0/1 knapsack (again), problem and inquiry about added functionality

B

Bubba

Greetings to all,

here's the code I have been assisted with few months ago on the group:

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

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

int main (void)
{
int c, n, i, s_err;

printf ("Enter number of objects: ");
s_err = scanf ("%d", &n);
if (s_err != 1)
{
fprintf (stderr, "Error inputing number of objects, terminating...\n");
exit(-2);
}

printf ("Enter knapsack capacity: ");
s_err = scanf ("%d", &c);
if (s_err != 1)
{
fprintf (stderr, "Error inputing capacity, terminating...\n");
exit(-2);
}

double **M = malloc ((n + 1) * sizeof *M);
for (i = 0 ; i < n + 1; i++)
if ((M = malloc ((c + 1) * sizeof *M)) == NULL)
break;
int *w = malloc (n * sizeof (w));
double *p = malloc (n * sizeof (p));

if (i != n + 1 || M == NULL || p == NULL || w == NULL)
{
fprintf (stderr, "Error allocating memory, terminating...\n");
exit(-1);
}

for (i = 0 ; i < n ; i++)
{
printf ("Enter weight of %d. object: ", i+1);
s_err = scanf ("%d", w+i);
if (s_err != 1)
{
fprintf (stderr, "Error inputing weight, terminating...\n");
exit(-2);
}
}

for (i = 0 ; i < n ; i++)
{
printf ("Enter value (price) of %d. object: ", i+1);
s_err = scanf ("%lf", p+i);
if (s_err != 1)
{
fprintf (stderr, "Error inputing weight, terminating...\n");
exit(-2);
}
}

printf ("%lf\n",zero_one_knapsack (n, c, M, w, p));

for (i = 0 ; i < n + 1 ; i++)
free(M);
free(M); free(w); free(p);

return 0;
}

Problem: I get errors like *** glibc detected *** free(): invalid next
size (fast): 0x0804a280 *** on Linux and Windows trigger a breakpoint
( Heap block at 00A94AF8 modified at 00A94B38 past requested size of
38; Invalid address specified to RtlValidateHeap( 00A90000, 00A94B00
). Any ideas why those that happen? All mallocs' seem to be properly
allocated, so I don't see where would the problem lie with free();...

New features req: what would be the "cheapest" way to figure out
what items are chosen in order to get maximum price for maximum
weight? Mathematically, I tried mangling something with permutations
and maximum values, but it gave no good result and it is rather
costly...

For example:

number of items = 5
knapsack weight = 10

w_1-5 = (2 3 4 1 9)
p_1-5 = (6 5 4 3 14)

Maximum weight is 18, and it is achieved with items 1, 2, 3 and 4.

Any hint or critics is, as always, appreciated.

Thanks in advance!
 
B

Ben Bacarisse

Bubba said:
here's the code I have been assisted with few months ago on the group:
double **M = malloc ((n + 1) * sizeof *M);
for (i = 0 ; i < n + 1; i++)
if ((M = malloc ((c + 1) * sizeof *M)) == NULL)
break;
int *w = malloc (n * sizeof (w));
double *p = malloc (n * sizeof (p));


These two don't follow the pattern on the ones above. To keep the
pattern you need:

int *w = malloc (n * sizeof *w);
double *p = malloc (n * sizeof *p);

The sizes are not going to be correct without the *s.

<snip>
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,982
Messages
2,570,185
Members
46,738
Latest member
JinaMacvit

Latest Threads

Top