# 0-1 Knapsack using dynamic programming in C

Recall that the 0-1 Knapsack problem is to fill a knapsack of given capacity with items of given weights and values in order to maximise the value of the knapsack’s contents. This can be solved in pseudo-polynomial time using dynamic programming.

This is another table-filling algorithm. The rows of the table represent items, and the columns are weights of the knapsack.

struct knapsack_entry {
unsigned int value;
unsigned int item;
struct knapsack_entry *prev;
};
typedef struct knapsack_entry knapsack_entry;

unsigned int knapsack(const unsigned int *weights, const unsigned int *values, size_t n,
unsigned int capacity, unsigned int **solution)
{
unsigned int i, j;
knapsack_entry **table;
unsigned int result;
knapsack_entry *head;

/* Allocate the table */
table = malloc((n + 1) * sizeof(knapsack_entry *));
for (i = 0; i <= n; i++) {
table[i] = malloc((capacity + 1) * sizeof(knapsack_entry));
}

/* Calculate the values and build chains */
for (i = 0; i <= n; i++) {
for (j = 0; j <= capacity; j++) {
if (i == 0 || j == 0) {
/* Initialising the first row or column */
table[i][j].value = 0;
table[i][j].item = 0;
table[i][j].prev = NULL;
}
else if (weights[i - 1] <= j) {
/* Can add item */
if (values[i - 1] + table[i - 1][j - weights[i - 1]].value
> table[i - 1][j].value) {
/* Add item */
table[i][j].value = values[i - 1] + table[i - 1][j - weights[i - 1]].value;
table[i][j].item = i - 1;
table[i][j].prev = &table[i - 1][j - weights[i - 1]];
}
else {
/* Don't add item */
table[i][j].value = table[i - 1][j].value;
table[i][j].item = table[i - 1][j].item;
table[i][j].prev = table[i - 1][j].prev;
}
}
else {
/* Don't add item */
table[i][j].value = table[i - 1][j].value;
table[i][j].item = table[i - 1][j].item;
table[i][j].prev = table[i - 1][j].prev;
}
}
}

/* Read back the solution */
*solution = calloc(n, sizeof(unsigned int));
for (i = 0, head = &table[n][capacity];
head->prev != NULL;
head = head->prev, i++) {
(*solution)[head->item] = 1;
}

result = table[n][capacity].value;
for (i = 0; i <= n; i++) {
free(table[i]);
}
free(table);
return result;
}


Here is an example program:

int main(void)
{
unsigned int weights[] = {2, 3, 4, 5, 9};
unsigned int values[] = {3, 4, 5, 8, 10};
const unsigned int capacity = 20;
const size_t n = sizeof(weights) / sizeof(weights[0]);
unsigned int *solution;
unsigned int value = knapsack(weights, values, n, capacity, &solution);
unsigned int i;
printf("Value: %u\n", value);
printf("Items in knapsack:\n");
for (i = 0; i < n; i++) {
if (solution[i]) {
printf("Item %u with weight %u and value %u\n", i, weights[i], values[i]);
}
}
free(solution);
return 0;
}


The output:

Value: 26
Items in knapsack:
Item 0 with weight 2 and value 3
Item 2 with weight 4 and value 5
Item 3 with weight 5 and value 8
Item 4 with weight 9 and value 10