0/1 Knapsack Problem
Definition
You have a bag (Knapsack) with a weight limit $W$. You have a list of items, each with a weight and a value. You want to maximize the total value in the bag without exceeding the weight limit. You cannot break items (0/1 property: either take it or leave it).
How it Works
For every item, you have a choice:
- Include it: Add its value to the total, subtract its weight from capacity.
- Exclude it: Skip it and keep the capacity the same.
- Result: max(Include, Exclude).
Code Example
PythonJavaCC++
# 0/1 Knapsack using Dynamic Programming
def knapSack(W, wt, val, n):
dp = [[0 for x in range(W + 1)] for x in range(n + 1)]
for i in range(n + 1):
for w in range(W + 1):
if i == 0 or w == 0:
dp[i][w] = 0
elif wt[i-1] <= w:
dp[i][w] = max(
val[i-1] + dp[i-1][w - wt[i-1]],
dp[i-1][w]
)
else:
dp[i][w] = dp[i-1][w]
return dp[n][W]
val = [60, 100, 120]
wt = [10, 20, 30]
W = 50
n = len(val)
print(knapSack(W, wt, val, n)) # 220
public class KnapsackDP {
static int knapSack(int W, int wt[], int val[], int n) {
int dp[][] = new int[n + 1][W + 1];
for (int i = 0; i <= n; i++) {
for (int w = 0; w <= W; w++) {
if (i == 0 || w == 0)
dp[i][w] = 0;
else if (wt[i-1] <= w)
dp[i][w] = Math.max(
val[i-1] + dp[i-1][w - wt[i-1]],
dp[i-1][w]
);
else
dp[i][w] = dp[i-1][w];
}
}
return dp[n][W];
}
public static void main(String[] args) {
int val[] = {60,100,120};
int wt[] = {10,20,30};
int W = 50;
System.out.println(knapSack(W, wt, val, val.length));
}
}
#include <stdio.h>
int max(int a, int b) {
return (a > b) ? a : b;
}
int knapSack(int W, int wt[], int val[], int n) {
int dp[n+1][W+1];
for (int i = 0; i <= n; i++) {
for (int w = 0; w <= W; w++) {
if (i == 0 || w == 0)
dp[i][w] = 0;
else if (wt[i-1] <= w)
dp[i][w] = max(
val[i-1] + dp[i-1][w - wt[i-1]],
dp[i-1][w]
);
else
dp[i][w] = dp[i-1][w];
}
}
return dp[n][W];
}
int main() {
int val[] = {60,100,120};
int wt[] = {10,20,30};
int W = 50;
printf("%d\n", knapSack(W, wt, val, 3));
return 0;
}
#include <iostream>
#include <vector>
using namespace std;
int knapSack(int W, vector<int> wt,
vector<int> val, int n) {
vector<vector<int>> dp(n+1,
vector<int>(W+1,0));
for (int i = 0; i <= n; i++) {
for (int w = 0; w <= W; w++) {
if (i == 0 || w == 0)
dp[i][w] = 0;
else if (wt[i-1] <= w)
dp[i][w] = max(
val[i-1] + dp[i-1][w - wt[i-1]],
dp[i-1][w]
);
else
dp[i][w] = dp[i-1][w];
}
}
return dp[n][W];
}
int main() {
vector<int> val = {60,100,120};
vector<int> wt = {10,20,30};
cout << knapSack(50, wt, val, val.size());
return 0;
}
Complexity Analysis
- Time Complexity: O(N times W) where N is number of items and W is capacity.
- Space Complexity: O(N times W.
Use Cases
- Resource Allocation: Budgeting money for projects.
- Cargo Loading: Optimizing truck/ship loads.