Kod:
#include <stdio.h>
#include <stdlib.h>
typedef struct {
char *name;
int weight;
int value;
int count;
} item_t;
#define REZERWA_parter 0.3
#define REZERWA 1
#define KNAPSACK_CAPACITY 50
#define NOF_KNAPSACKS 4
item_t items[] = {
{"1", 5+REZERWA_parter, 1, 1},
{"2", 5+REZERWA_parter, 1, 1},
{"3", 6.2+REZERWA_parter, 1, 1},
{"4", 12.5+REZERWA_parter, 1, 1},
{"5", 12.5+REZERWA_parter, 1, 1},
{"6", 12.5+REZERWA_parter, 1, 1},
{"7", 8.7+REZERWA_parter, 1, 1},
{"8", 8.7+REZERWA_parter, 1, 1},
{"9", 6.5+REZERWA_parter, 1, 1},
{"10", 6.5+REZERWA_parter, 1, 1},
{"11", 3.5+REZERWA_parter, 1, 1},
{"12", 3.5+REZERWA_parter, 1, 1},
{"13", 8+REZERWA, 1, 1},
{"14", 8+REZERWA, 1, 1},
{"15", 10+REZERWA, 1, 1},
{"16", 10+REZERWA, 1, 1},
{"17", 4.5+REZERWA, 1, 1},
{"18", 4.5+REZERWA, 1, 1},
{"19", 4+REZERWA, 1, 1},
{"20", 5.5+REZERWA, 1, 1},
{"21", 5.5+REZERWA, 1, 1},
{"22", 3.5+REZERWA, 1, 1},
{"23", 3.5+REZERWA, 1, 1},
{"24", 3.5+REZERWA, 1, 1},
{"25", 1+REZERWA, 1, 1},
{"26", 1+REZERWA, 1, 1},
{"27", 5+REZERWA, 1, 1},
{"28", 5+REZERWA, 1, 1},
{"29", 6+REZERWA, 1, 1},
{"30", 6+REZERWA, 1, 1},
{"31", 3+REZERWA, 1, 1},
{"32", 3+REZERWA, 1, 1},
{"33", 4+REZERWA, 1, 1},
{"34", 4+REZERWA, 1, 1},
};
int n = sizeof (items) / sizeof (item_t);
int *knapsack (int w) {
int i, j, k, v, *mm, **m, *s;
mm = calloc((n + 1) * (w + 1), sizeof (int));
m = malloc((n + 1) * sizeof (int *));
m[0] = mm;
for (i = 1; i <= n; i++) {
m[i] = &mm[i * (w + 1)];
for (j = 0; j <= w; j++) {
m[i][j] = m[i - 1][j];
for (k = 1; k <= items[i - 1].count; k++) {
if (k * items[i - 1].weight > j) {
break;
}
v = m[i - 1][j - k * items[i - 1].weight] + k * items[i - 1].value;
if (v > m[i][j]) {
m[i][j] = v;
}
}
}
}
s = calloc(n, sizeof (int));
for (i = n, j = w; i > 0; i--) {
int v = m[i][j];
for (k = 0; v != m[i - 1][j] + k * items[i - 1].value; k++) {
s[i - 1]++;
j -= items[i - 1].weight;
}
}
free(mm);
free(m);
return s;
}
int main () {
int i, tc = 0, tw = 0, tv = 0, *s;
for (i = 0; i < n; i++) {
items[i].value = items[i].weight;
}
for(int k = 0; k < NOF_KNAPSACKS; k++)
{
tc = 0;
tw = 0;
tv = 0;
s = knapsack(KNAPSACK_CAPACITY);
for (i = 0; i < n; i++) {
if (s[i]) {
printf("%-22s %5d\n", items[i].name, s[i] * items[i].weight);
tc += s[i];
tw += s[i] * items[i].weight;
tv += s[i] * items[i].value;
items[i].weight = 10000;
items[i].value = 0;
}
}
printf("%-22s %5d %5d\n\n", "count, weight:", tc, tw);
}
printf("Items not packed:\n");
for (i = 0; i < n; i++) {
if (items[i].value) {
printf("%-22s %5d \n", items[i].name, items[i].weight );
}
}
return 0;
}