0/1 Knapsack problem, what am I doing wrong

0/1 Knapsack problem, what am I doing wrong

Post by Eric Sosma » Thu, 23 Apr 2009 06:40:00



if ( j >= w[i-1] )


if ((M[i-1][j-w[i-1]] + p[i-1]) > M[i-1][j]) M[i][j]


= M[i-1][j-w[i-1]] + p[i-1];


--
XXXX@XXXXX.COM
 
 
 

0/1 Knapsack problem, what am I doing wrong

Post by Bubb » Thu, 23 Apr 2009 06:48:49

Eric Sosman's log on stardate 21 tra 2009


Eric, that was flawless! I am speechless. Thank you very very very much
for your fast and accurate reaction!

--
Everything will be okay
in the end.
If it's not okay
it's not the end!

 
 
 

0/1 Knapsack problem, what am I doing wrong

Post by Bubb » Thu, 23 Apr 2009 08:14:14

Eric Sosman's log on stardate 21 tra 2009

/snip

Incredible.

Here's the code now:

#include <stdio.h>

double zero_one_knapsack (int n, int c, double **M, double *w, double *p)
{
int i, j;
for (i=0; i<=n; i++) M[i][0] = 0;
for (j=0; j<=c; j++) M[0][j] = 0;
for (i=1; i<=n; i++)
for (j=1; j<=c; j++)
{
M[i][j] = M[i-1][j];
if ( j >= w[i-1] )
if ((M[i-1][j-(int)w[i-1]] + (int)p[i-1]) > M[i-1][j]) M[i][j]
= M[i-1][j-(int)w[i-1]] + (int)p[i-1];
}
return M[n][c];
}

int main (void)
{
int c, n, i;
printf ("Enter number of objects: ");
scanf ("%d", &n);
printf ("Enter knapsack capacity: ");
scanf ("%d", &c);
double **M = (double **)malloc (n + 1 * sizeof (double *));
for (i = 0 ; i < n + 1; i++)
M[i] = (double *)malloc (c + 1 * sizeof (double));
double *w = (double *)malloc (n * sizeof (double));
double *p = (double *)malloc (n * sizeof (double));
for (i = 0 ; i < n ; i++)
{
printf ("Enter weight of %d. object: ", i+1);
scanf ("%lf", w+i);
}
for (i = 0 ; i < n ; i++)
{
printf ("Enter value (price) of %d. object: ", i+1);
scanf ("%lf", p+i);
}
printf ("%f\n",zero_one_knapsack (n, c, M, w, p));
return 0;
}

Compiling on VS 2008 returns 9.000000 but doing the same thing on gcc
version 4.1.2 (x86, Debian) returns 7.000000 (based on the parameters
in the original post)?

What am I doing wrong now?

--
Everything will be okay
in the end.
If it's not okay
it's not the end!
 
 
 

0/1 Knapsack problem, what am I doing wrong

Post by Bubb » Thu, 23 Apr 2009 08:15:28

Bubba's log on stardate 22 tra 2009


Sorry, copied the code without #include <stdlib.h>.

--
Everything will be okay
in the end.
If it's not okay
it's not the end!
 
 
 

0/1 Knapsack problem, what am I doing wrong

Post by Chris McDo » Thu, 23 Apr 2009 08:19:40

Bubba < XXXX@XXXXX.COM > writes:


I'm "troubled" by the indentation in the above.
The 2nd loop is not "inside" the 1st, but indentation suggests otherwise.

I'm unfamiliar with the algorithm but I feel that you initial confusion,
so quickly addressed by Eric is due to the indicies i and j sometimes
starting at 0, and othertimes from 1 (??).



Do you mean
double **M = (double **)malloc ((n + 1) * sizeof (double *));

and

M[i] = (double *)malloc ((c + 1) * sizeof (double));

--
Chris.
 
 
 

0/1 Knapsack problem, what am I doing wrong

Post by Bubb » Thu, 23 Apr 2009 08:41:52

Chris McDonald's log on stardate 22 tra 2009


That one is OK, the "trouble" part really is only in indentation. It
should have been written like this:

for (i=0; i<=n; i++) M[i][0] = 0;
for (j=0; j<=c; j++) M[0][j] = 0;
for (i=1; i<=n; i++)
for (j=1; j<=c; j++)


Naturally! Once again, knitting code at 2 AM was not such great idea after
all...

Still, it puzzles me how on earth VS managed to compute the right result.
Never mind, though, as it works as it should now!

Thank you for your swift intervention! :)

--
Everything will be okay
in the end.
If it's not okay
it's not the end!
 
 
 

0/1 Knapsack problem, what am I doing wrong

Post by Keith Thom » Thu, 23 Apr 2009 09:47:47

Bubba < XXXX@XXXXX.COM > writes:

No, the third line should be at the same level as the second:

for (i=0; i<=n; i++) M[i][0] = 0;
for (j=0; j<=c; j++) M[0][j] = 0;
for (i=1; i<=n; i++)
for (j=1; j<=c; j++)

Or, for even greater clarity IMHO):

for (i=0; i<=n; i++)
M[i][0] = 0;
for (j=0; j<=c; j++)
M[0][j] = 0;
for (i=1; i<=n; i++)
for (j=1; j<=c; j++)

Actually, I'd write it as:

for (i = 0; i <= n; i++) {
M[i][0] = 0;
}
for (j = 0; j <= c; j++) {
M[0][j] = 0;
}
for (i = 1; i <= n; i++) {
for (j = 1; j <= c; j++) {
/* ... */
}
}

--
Keith Thompson (The_Other_Keith) XXXX@XXXXX.COM < http://www.yqcomputer.com/ ~kst>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
 
 
 

0/1 Knapsack problem, what am I doing wrong

Post by Bubb » Thu, 23 Apr 2009 17:38:25

Keith Thompson's log on stardate 22 tra 2009

/snip

True. :) As I said, let's blame it on being tired... :)

Here's the whole code, BTW, as far as I've tested it, it works flawless
and I hope it meets all relevant C programming guidelines now. :)

#include <stdio.h>
#include <stdlib.h>

double zero_one_knapsack (int n, int c, double **M, double *w, double *p)
{
int i, j;
for (i=0; i<=n; i++)
{
M[i][0] = 0;
}
for (j=0; j<=c; j++)
{
M[0][j] = 0;
}
for (i=1; i<=n; i++)
{
for (j=1; j<=c; j++)
{
M[i][j] = M[i-1][j];
if ( j >= w[i-1] )
{
if ((M[i-1][j-(int)w[i-1]] + (int)p[i-1]) > M[i-1][j]) M[i][j]
= M[i-1][j-(int)w[i-1]] + (int)p[i-1];
}
}
return M[n][c];
}

int main (void)
{
int c, n, i;
printf ("Enter number of objects: ");
scanf ("%d", &n);
printf ("Enter knapsack capacity: ");
scanf ("%d", &c);
double **M = (double **)malloc ((n + 1) * sizeof (double *));
for (i = 0 ; i < n + 1; i++)
M[i] = (double *)malloc ((c + 1) * sizeof (double));
double *w = (double *)malloc (n * sizeof (double));
double *p = (double *)malloc (n * sizeof (double));
if (M == NULL || p == NULL || w == NULL)
{
fprintf (stderr, "Error allocating memory, terminating...");
exit(1);
}
for (i = 0 ; i < n ; i++)
{
printf ("Enter weight of %d. object: ", i+1);
scanf ("%lf", w+i);
}
for (i = 0 ; i < n ; i++)
{
printf ("Enter value (price) of %d. object: ", i+1);
scanf ("%lf", p+i);
}
printf ("%f\n",zero_one_knapsack (n, c, M, w, p));
for (i = 0 ; i < n + 1 ; i++)
free(M[i]);
free(M); free(w); free(p);
return 0;
}


Thanks once again to all three of you for your altruistic aid. :)

--
Everything will be okay
in the end.
If it's not okay
it's not the end!
 
 
 

0/1 Knapsack problem, what am I doing wrong

Post by Ben Bacari » Thu, 23 Apr 2009 22:05:45

ubba < XXXX@XXXXX.COM > writes:


A few comments...


Missing } here!


Why is everything double? When w[x] and p[x] are used, they must be
converted to int so the effect is that M only holds integers. Using
only integers would simplify a few things.


It is usually a good idea to test the scanf returns the correct count
(1 in this case). You could have a function that prompts and then
reads an int. This may see like a lot of work for a few cases, but
programming is cumulative. The program you write tomorrow might
benefit from this function so it is almost always worth writing it
now.


I'd write:

double **M = malloc((n + 1) * sizeof *M);


Same here (and below). This one looks more complex but the pattern is
the same:

M[i] = malloc ((c + 1) * sizeof *M[i]);

Note that if you do this and decide to switch to int rather than
double, none of the malloc calls need to change.

Small point: you are not being consistent. Some of your one-line
loops have {}s and some don't. I favour not having them, but many
people feel differently. Consistency is probably more important than
which of these options you choose.


This worries me. It is possible that one of the row allocations in
the loop above could fail, while those for w and p might succeed. You
need to test inside the loop as well. I'd probably write:

for (i = 0 ; i < n + 1; i++)
if ((M[i] = malloc ((c + 1) * sizeof *M[i])) == NULL)
break;

and then test that the loop ran to the end:

if (i != n + 1 || M == NULL || p == NULL || w == NULL)



You might want to look at the C FAQ. 6.16 is all about allocating
multi-dimensional arrays. http://c-faq.com/aryptr/dynmuldimary.html

--
Ben.
 
 
 

0/1 Knapsack problem, what am I doing wrong

Post by Bubb » Fri, 24 Apr 2009 04:27:38

Ben Bacarisse's log on stardate 22 tra 2009


Thx, I was secretly hoping for something like that... ;)


Noted. I removed all unnecessary parenthesizes.


Indeed, this actually, when I look at the algorithm and the code makes
sense...


Something like this? I could call a function for this one, but just as a
concept, is ti OK?

int s_err;
...
s_err = scanf ("%d", &c);
if (s_err != 1 || s_err == EOF)
{
fprintf (stderr, "Error inputing capacity, terminating...");
exit(2);
}


I did as you suggested, but can you clarify the reasons for such
intervention?[1]


I did switch to int and removed the casts.


Critics noted. I agree and also dislike {} on oneliners and am naturally
sloppy... :)


Thx, yes, I forgot to check the rows allocation...


I did when I wrote the code, that's why I'm perplexed with the
intervention [1]. :)

Thx a lot for your kind comments.

Best regards.

--
Everything will be okay
in the end.
If it's not okay
it's not the end!
 
 
 

0/1 Knapsack problem, what am I doing wrong

Post by gw7ri » Fri, 24 Apr 2009 05:41:29


> for (i = 0; < <= n; i++) {> > M[i][0] > 0;
>>}
> for <j = 0; j <= c> j++) {
> >[0][j] = 0;
> }

Is it just me, or does that look horrible? If you must use brackets,
and if you want to use additional lines (I normally only use the extra
lines if lines are getting too long, which isn't the case here) what's
wrong with:

< for (i = 0; i <= n; i++) {
M[i][0] = 0; }
< for (j = 0; j <= c; j++) {
M[0][j] = 0; }

The indenting makes it perfectly clear what is>controlled.

> Keith Thompson (The_Other_Keith)

And while I'm here - what does this refer to? Which other Keith? And
wouldn't "The other K Thompson" have more cachet?
 
 
 

0/1 Knapsack problem, what am I doing wrong

Post by Keith Thom » Fri, 24 Apr 2009 06:01:28


XXXX@XXXXX.COM writes:

>>>> }
>> for (< = 0; j <= c>>j++) {
>> >>0][j] > 0>
>> }
>
> Is it just me, or does that look horrible? If you must>use brackets,
> and if you want to use additional lines (I normally only>use the extra
> lines if lines are getting too long, which isn't the cas> here) what's >> >rong with:
>
> fo< (i = 0; > <= n; i++) {
> >[i][0] = 0; }
> fo< (j = 0; > <= c; j++) {
> >[0>[j] = 0; }
>
> The indenting makes it perfectly clear what is controlled.

It's a matter of taste. The style I use for brace layout is basically
what's used in K&R (except that K&R tends to leave out optional
braces, and I almost always include them).

It's sometimes called the One True Brace Style; see Henry Spencer's
8t< Commandment, < http://www.yqcomputer.com/ ;mmandments.html>.

I'm not sure I have a logical argument against putting the closing
brace at the end of the line, but I personally dislike it, and it's
not a common style. In any case, if you're going to be reading a lot
of C code, you'd better at least get used to seeing the OTBS.

On the other hand, if I'm working on existing code, I'll follow the
conventions established i>>that code.

>> Keith Thompson (Th>_O>her_Keith)
>
> And while I'm here - what does this refer to? Which ot>er Keith? And
> wouldn't "The other K Thompson" have more<cachet? >

When I started my first job out of college, there was another person
at the company named Keith. I've continued using it in my .sig long
after it became i<relevant.>


--
Keith Thompson (The_Other_Keith) < XXXX@XXXXX.COM
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
 
 
 

0/1 Knapsack problem, what am I doing wrong

Post by James Kuyp » Fri, 24 Apr 2009 08:17:07


...

sizeof(double) and sizeof *M[i] give the same quantity; so it might seem
that it doesn't matter which one you use. However, if at any future time
the code might need modification, then it does make a difference.

If you change the type of M, sizeof(double) will be incorrect, while
sizeof *M[i] will still be correct.

Of course, there's the flip side of the issue: what if you change the
name of 'M' rather than it's type. In that case, sizeof(double) will
remain the same, whereas sizeof *M[i] will be incorrect.

However, there's two key differences between the two options: if you
change the variable name without changing the sizeof expression, you'll
generally get an error based upon the fact that the old variable name is
no longer defined. Secondly, you can verify whether sizeof *M[i] is
correct just by looking at the left operand of the '=' operator;
verifying whether sizeof(double) is correct will require searching for
the declaration of 'M'. It's certainly possible to do such a search, but
it's a lot more work than verifying.

The second change is removing the cast. This cast is unnecessary,
because it does precisely the same thing that will happen anyway if the
cast were not present. Cases where casts are really necessary are rare,
and are always dangerous; casts should only be used in those situations,
and everytime you see a cast you should automatically think to yourself:
"gomething tricky is going on here, I need to make sure that it's
actually correct". Whenever you use casts where they aren't needed, you
encourage a tendency to ignore casts - and that's bad.

There's a second reason that's specific to C90. If you try to call
malloc() without having a declaration of that function in scope, in C99
it's a constraint violation. However, in C90, in that same situation,
the compiler will create an implicit declaration of malloc() as a
function returning an int. Since malloc() actually returns a void*, this
is an error, though it will accidentally work as intended on some
machines where 'int' and 'void*' have the same size. Without the cast,
you have a constraint violation and the implementation is required to
issue a diagnostic. However, with the cast, it is not a constraint
violation, and no diagnostic is required. In other words, the cast turns
off the diagnostic, and it's a diagnostic you should really want to recieve.
 
 
 

0/1 Knapsack problem, what am I doing wrong

Post by Ben Bacari » Fri, 24 Apr 2009 09:54:16

Bubba < XXXX@XXXXX.COM > writes:

<snip>
<snip>

The two tests are redundant since EOF is negative but, yes, that kind
of thing. Now that everything is integer-based, one function could be
written to prompt for and read a number. You'd use it all over the
place.

<snip>

See James' excellent reply.


You mean you wonder why I suggested one form and the C FAQ uses
another? Who knows? It is small matter of style, but there are
enough things going for the

<exp> = malloc(<size> * sizeof *<exp>);

pattern that I now use it almost always but writing sizeof(<type>) is
not wrong. Note that almost everyone agrees that not casting malloc
is the right thing to do in C.

--
Ben.