# 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;

/* 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) {
if (values[i - 1] + table[i - 1][j - weights[i - 1]].value
> table[i - 1][j].value) {
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 {
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 {
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];
}

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


# 0-1 Knapsack using backtracking in C

In the 0-1 Knapsack problem, we are given a set of items with individual weights and profits and a container of fixed capacity (the knapsack), and are required to compute a loading of the knapsack with items such that the total profit is maximised. We only have 1 of each item, so there is either 0 or 1 of each item in in the knapsack, hence the 0-1 in the name of the problem.

The 0-1 knapsack problem is NP-hard, but can be solved quite efficiently using backtracking. Below is a backtracking implementation in C. The function knapsack() takes arrays of weights, and profits, their size, the capacity, and the address of a pointer through which the solution array is returned. It returns the profit of the best knapsack. The profit density of each item (weight / profit) is first calculated, and the knapsack is filled in order of decreasing profit density. A bounding function is used to determine the upper bound on the profit achievable with the current knapsack so as to reduce the search space.

#include <stdlib.h>
#include <string.h>

/* A knapsack item */
typedef struct {
unsigned int id;
double weight;
double profit;
double profit_density;
} item;

/* Compare items by lesser profit density */
static int compare_items(const item *item1, const item *item2)
{
if (item1->profit_density > item2->profit_density) {
return -1;
}
if (item1->profit_density < item2->profit_density) {
return 1;
}
return 0;
}

/* Bounding function */
static double profit_bound(const item *items, size_t n, double capacity,
double current_weight, double current_profit,
unsigned int level)
{
double remaining_capacity = capacity - current_weight;
double bound = current_profit;
unsigned int lvl = level;
/* Fill in order of decreasing profit density */
while (lvl < n &&
items[lvl].weight <= remaining_capacity)
{
remaining_capacity -= items[lvl].weight;
bound += items[lvl].profit;
lvl++;
}
/* Pretend we can take a fraction of the next object */
if (lvl < n) {
bound += items[lvl].profit_density
* remaining_capacity;
}
return bound;
}

static void knapsack_recursive(const item *items, size_t n, double capacity,
unsigned int *current_knapsack, double *current_weight, double *current_profit,
unsigned int *max_knapsack, double *max_profit, unsigned int level)
{
if (level == n) {
/* Found a new max knapsack */
*max_profit = *current_profit;
memcpy(max_knapsack, current_knapsack, n * sizeof(unsigned int));
return;
}
if (*current_weight + items[level].weight <= capacity)
{   /* Try adding this item */
*current_weight += items[level].weight;
*current_profit += items[level].profit;
current_knapsack[items[level].id] = 1;
knapsack_recursive(items, n, capacity, current_knapsack, current_weight,
current_profit, max_knapsack, max_profit, level + 1);
*current_weight -= items[level].weight;
*current_profit -= items[level].profit;
current_knapsack[items[level].id] = 0;
}
if (profit_bound(items, n, capacity, *current_weight,
*current_profit, level + 1) > *max_profit) {
/* Still promising */
knapsack_recursive(items, n, capacity, current_knapsack, current_weight,
current_profit, max_knapsack, max_profit, level + 1);
}
}

double knapsack(const double *weights, const double *profits,
size_t n, double capacity, unsigned int **max_knapsack)
{
double current_weight = 0.0;
double current_profit = 0.0;
double max_profit = 0.0;
unsigned int i;
item *items  = malloc(n * sizeof(item));
unsigned int *current_knapsack = calloc(n, sizeof(unsigned int));
*max_knapsack = malloc(n * sizeof(unsigned int));
if (!(items && current_knapsack && *max_knapsack)) {
free(items);
free(current_knapsack);
free(*max_knapsack);
*max_knapsack = NULL;
return 0;
}
/* Populate the array of items */
for (i = 0; i < n; i++) {
items[i].id = i;
items[i].weight = weights[i];
items[i].profit = profits[i];
items[i].profit_density = profits[i] / weights[i];
}
/* Sort into decreasing density order */
qsort(items, n, sizeof(item),
(int (*)(const void *, const void *))compare_items);
knapsack_recursive(items, n, capacity, current_knapsack, &current_weight,
&current_profit, *max_knapsack, &max_profit, 0);
free(items);
free(current_knapsack);
return max_profit;
}


Here is an example program:

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

int main(void)
{
double weights[] = {3, 5, 2, 1};
double profits[] = {9, 10, 7, 4};
const size_t n = sizeof(profits) / sizeof(profits[0]);
const double capacity = 7;
unsigned int *max_knapsack;
double max_profit = knapsack(weights, profits, n, capacity, &max_knapsack);
unsigned int i;
printf("Profit: %.2f\n", max_profit);
printf("Knapsack contains:\n");
for (i = 0; i < n; i++) {
if (max_knapsack[i] == 1) {
printf("Item %u with weight %.2f and profit %.2f\n", i, weights[i], profits[i]);
}
}
free(max_knapsack);
return 0;
}


The output:

Profit: 20.00
Knapsack contains:
Item 0 with weight 3.00 and profit 9.00
Item 2 with weight 2.00 and profit 7.00
Item 3 with weight 1.00 and profit 4.00