|
Od sto glasa i silnih petica u indexu, ah...
No dobro. Ako ce ikome ustrebati, evo citav kod (ispravljena funkcija zero_one_knapsack iz skripte) s dinamickom alokacijom svih parametara (kapacitet ranca, broj objekata i njihova tezina i cijena) [strike]no i bez provjere uspjesne alokacije istih (koga veseli, siroko vam if polje)[/strike].
[code:1]#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[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-w[i-1]] + p[i-1]) > M[i-1][j])
M[i][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[i] = malloc ((c + 1) * sizeof *M[i])) == 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[i]);
free(M); free(w); free(p);
return 0;
}
[/code:1]
HTH,
Bubba
[size=7]Ljepiti kod po forumu u dva ujutro je glupo. Evo ispravljena verzija. Valjda je sada sve OK... :) Edit2: eto, opet nova, doradjenija i malo portabilnija verzija...[/size]
Od sto glasa i silnih petica u indexu, ah...
No dobro. Ako ce ikome ustrebati, evo citav kod (ispravljena funkcija zero_one_knapsack iz skripte) s dinamickom alokacijom svih parametara (kapacitet ranca, broj objekata i njihova tezina i cijena) no i bez provjere uspjesne alokacije istih (koga veseli, siroko vam if polje).
| Kod: | #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[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-w[i-1]] + p[i-1]) > M[i-1][j])
M[i][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[i] = malloc ((c + 1) * sizeof *M[i])) == 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[i]);
free(M); free(w); free(p);
return 0;
}
|
HTH,
Bubba
Ljepiti kod po forumu u dva ujutro je glupo. Evo ispravljena verzija. Valjda je sada sve OK...  Edit2: eto, opet nova, doradjenija i malo portabilnija verzija...
_________________ Biolozi misle da su kemičari. Kemičari misle da su fizičari. Fizičari misle da su bogovi. A Bog misli da je matematičar...
§ http://math2.ath.cx § |
