0-1 Knapsack
A thief brings a bag that can carry C = 20 kilograms into a shop. How should items be selected to maximize their value?
| Item | Weight W | Value V |
|---|---|---|
| 0 | 2 | 3 |
| 1 | 3 | 4 |
| 2 | 4 | 5 |
| 3 | 5 | 8 |
| 4 | 9 | 10 |
Let B(k,C) be the greatest value obtainable from the first k items with capacity C. Items are numbered from 0, so the last of these k items has index k−1.
The boundaries are B(i,0) = B(0,j) = 0: if capacity is zero or no items remain, the maximum value is zero.
0-1 knapsack: take or skip, fill states and recover items
Unlock the complete interactive lab, deeper explanations, and curated reference answers.
0-1 knapsack
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct {
int weight;
int value;
} Item;
Item item_create(int weight, int value) {
Item item;
item.weight = weight;
item.value = value;
return item;
}
static int max_int(int a, int b) {
return a > b ? a : b;
}
int knapsack(Item *items, int n, int capacity) {
int values[n + 1][capacity + 1];
memset(values, 0, sizeof(values));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= capacity; j++) {
if (items[i - 1].weight > j) {
values[i][j] = values[i - 1][j];
} else {
values[i][j] = max_int(
values[i - 1][j - items[i - 1].weight] + items[i - 1].value,
values[i - 1][j]
);
}
}
}
return values[n][capacity];
}
int main(void) {
Item items[] = {
item_create(2, 3),
item_create(3, 4),
item_create(4, 5),
item_create(5, 8),
item_create(9, 10),
};
int n = sizeof(items) / sizeof(Item);
int capacity = 20;
printf("%d\n", knapsack(items, n, capacity));
return 0;
}Weights are positive integers; values and capacity are nonnegative integers. Each item can be taken at most once.
KNOWLEDGE QUIZ
KNOWLEDGE QUIZ
Compare take/skip and recover the items
w=2, v=4
w=3, v=5
w=4, v=7
Capacity 7; use each item at most once. Show the states for capacities 0–7 after each item, identify take/skip dependencies, and recover the best selection.