The 0-1 knapsack problem asks: given a set of items each with a weight and a value, and a knapsack with a maximum weight capacity, which items should you pack to maximize the total value? Each item can be taken once (0-1) — you cannot take a fraction. This is a classic dynamic programming problem that appears in interview questions, resource allocation, and combinatorial optimization.
Problem Statement
Items: 4 Weights: [2, 3, 4, 5] Values: [3, 4, 5, 6] Capacity: 8 Find the subset with maximum total value ≤ capacity 8.
How Dynamic Programming Solves It
Build a 2D table dp[i][w] where:
i= number of items considered (0 to n)w= knapsack capacity considered (0 to W)dp[i][w]= maximum value achievable using the first i items with capacity w
Recurrence relation:
if weight[i] > w:
dp[i][w] = dp[i-1][w] /* can't fit item i */
else:
dp[i][w] = max(dp[i-1][w], /* skip item i */
value[i] + dp[i-1][w - weight[i]]) /* take item i */
C Program for 0-1 Knapsack
#include <stdio.h>
#include <stdlib.h>
#define MAX(a, b) ((a) > (b) ? (a) : (b))
int main(void)
{
int weights[] = {2, 3, 4, 5};
int values[] = {3, 4, 5, 6};
int n = 4;
int capacity = 8;
int **dp;
int i, w, max_val;
/* Allocate dp[n+1][capacity+1] */
dp = (int **)malloc((n + 1) * sizeof(int *));
for (i = 0; i <= n; i++)
dp[i] = (int *)malloc((capacity + 1) * sizeof(int));
/* Base cases */
for (i = 0; i <= n; i++) dp[i][0] = 0;
for (w = 0; w <= capacity; w++) dp[0][w] = 0;
/* Fill table bottom-up */
for (i = 1; i <= n; i++) {
for (w = 1; w <= capacity; w++) {
if (weights[i - 1] <= w)
dp[i][w] = MAX(values[i - 1] + dp[i - 1][w - weights[i - 1]],
dp[i - 1][w]);
else
dp[i][w] = dp[i - 1][w];
}
}
max_val = dp[n][capacity];
printf("Maximum value: %d\n\n", max_val);
/* Traceback to find which items were selected */
printf("Items selected:\n");
i = n; w = capacity;
while (i > 0 && w > 0) {
if (dp[i][w] != dp[i - 1][w]) {
printf(" Item %d: weight=%d, value=%d\n",
i, weights[i - 1], values[i - 1]);
w -= weights[i - 1];
}
i--;
}
for (i = 0; i <= n; i++) free(dp[i]);
free(dp);
return 0;
}
Output
Maximum value: 10 Items selected: Item 4: weight=5, value=6 Item 2: weight=3, value=4
Items 2 and 4 together: weight = 3 + 5 = 8 (exactly at capacity), value = 4 + 6 = 10. No other subset gives a higher value within capacity 8.
DP Table Trace
The full table shows how the maximum value builds up row by row as each item is considered:
Capacity → 0 1 2 3 4 5 6 7 8 i=0 (none): 0 0 0 0 0 0 0 0 0 i=1 (w=2): 0 0 3 3 3 3 3 3 3 i=2 (w=3): 0 0 3 4 4 7 7 7 7 i=3 (w=4): 0 0 3 4 5 7 8 9 9 i=4 (w=5): 0 0 3 4 5 7 8 9 10
Reading the table: at capacity 8 with all 4 items considered, the answer is dp[4][8] = 10.
Traceback: dp[4][8] = 10 ≠ dp[3][8] = 9 → Item 4 was taken (w=5), move to dp[3][3]. dp[3][3] = 4 ≠ dp[2][3] = 4… actually dp[3][3] = dp[2][3] so Item 3 was skipped. dp[2][3] = 4 ≠ dp[1][3] = 3 → Item 2 was taken (w=3), done.
How to Compile and Run
gcc -ansi -Wall -Wextra knapsack.c -o knapsack
./knapsack
Time and Space Complexity
| Metric | Value | Reason |
|---|---|---|
| Time | O(n × W) | Two nested loops: n items × W capacity values |
| Space | O(n × W) | The full DP table; reducible to O(W) with 1D rolling array |
This is pseudo-polynomial time — it depends on the numeric value of W, not just the number of items. The 0-1 knapsack problem is NP-complete in general; DP gives the optimal solution when W is small enough to store the table.
Common Variations
| Variant | Change |
|---|---|
| Unbounded knapsack | Items can be taken any number of times — change dp[i-1] to dp[i] in the “take” branch |
| Fractional knapsack | Items can be split — use a greedy value/weight ratio sort instead of DP |
| Space-optimised 0-1 | Use a 1D array, iterate capacity right-to-left to avoid counting an item twice |
Related Programs
- Binary Search in C
- Merge Sort in C
- Recursion in C – Complete Guide
- Pointers in C – malloc and pointer-to-pointer
Recommended Books
- The C Programming Language – Kernighan & Ritchie (India) | Amazon.com
- C Programming: A Modern Approach – K.N. King (India) | Amazon.com
Practice DP problems with the C Programming Quiz App — 500+ MCQs covering algorithms, recursion, and more.
Download on Google Play →