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