Re: 0/1 Knapsack problem, what am I doing wrong

Ben Bacarisse's log on stardate 22 tra 2009

A few comments...

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

Missing } here!

Noted. I removed all unnecessary parenthesizes.

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.

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

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.

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);
}

printf ("Enter knapsack capacity: ");
scanf ("%d", &c);
double **M = (double **)malloc ((n + 1) * sizeof (double *));

I'd write:

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

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

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

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

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

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

I did switch to int and removed the casts.

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.

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

double *w = (double *)malloc (n * sizeof (double));
double *p = (double *)malloc (n * sizeof (double));
if (M == NULL || p == NULL || w == NULL)

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)

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

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

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!
.

Relevant Pages

  • Re: Hashtable
    ... public void AddKeyedValue(string key, int value) { ... Justin Rogers ... Blog: http://weblogs.asp.net/justin_rogers "MAY" wrote in message ... > Thx again. ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: weird problem
    ... >> when I calculate it on a calculator ... so the debugger displayed 40 but in reality it ... was rounded off to 39 when casted to int. ... Thx for your reply ...
    (microsoft.public.vc.language)
  • Re: convert a string to all-lowercase string
    ... (I'm a newbye) ... Thx for the help:) ... int main{ ... if(isupper((unsigned char) c)) ...
    (comp.lang.c)
  • How to trigger onCreate (COleControl) in Edit-mode PowerPoint
    ... thx. ... Dankung ... MPLEMENT_DYNCREATE(MyCtrl, COleControl) ... int MyCtrl::OnCreate ...
    (microsoft.public.office.developer.automation)
  • Re: convert a string to all-lowercase string
    ... (I'm a newbye) ... Thx for the help:) ... int main{ ... if(isupper((unsigned char) c)) ...
    (comp.lang.c)