Practice › Dynamic Programming
0/1 Knapsack
Medium · Dynamic Programming · Asked at Amazon, Microsoft, Google, Flipkart
Each item has a weight and a value and can be taken at most once. Maximise the total value without exceeding capacity W.
Input
First line: n W. Second line: n weights. Third line: n values.
Output
The maximum total value.
Constraints
- 1 ≤ n ≤ 1000
- 1 ≤ W ≤ 1000
- 1 ≤ weight, value ≤ 1000
dp[w] over capacities, iterating w downwards so each item is used once.
Example 1
Input
3 4 4 5 1 1 2 3
Output
3
Example 2
Input
3 3 4 5 6 1 2 3
Output
0
Hints
- dp[w] = best value achievable with total weight ≤ w using the items processed so far.
- For each item, loop w DOWNWARDS from W to its weight: dp[w] = max(dp[w], dp[w − weight] + value). Going down stops the item being used twice.
Approach
This is the 1-D form of the classic table dp[item][capacity]. For each item (weight wt, value v), update capacities from W down to wt: dp[w] = max(dp[w], dp[w − wt] + v). Iterating downwards means dp[w − wt] still holds the value from before this item, so each item is taken at most once. Iterating upwards would give the unbounded knapsack. The answer is dp[W].
Complexity: O(n · W) time · O(W) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, W;
cin >> n >> W;
vector<int> wt(n), val(n);
for (auto &x : wt) cin >> x;
for (auto &x : val) cin >> x;
vector<long long> dp(W + 1, 0);
for (int i = 0; i < n; i++)
for (int w = W; w >= wt[i]; w--) dp[w] = max(dp[w], dp[w - wt[i]] + val[i]);
cout << dp[W] << "\n";
return 0;
}Python solution
import sys
data = list(map(int, sys.stdin.read().split()))
n, W = data[0], data[1]
wt = data[2 : 2 + n]
val = data[2 + n : 2 + 2 * n]
dp = [0] * (W + 1)
for i in range(n):
w_i, v_i = wt[i], val[i]
for w in range(W, w_i - 1, -1):
if dp[w - w_i] + v_i > dp[w]:
dp[w] = dp[w - w_i] + v_i
print(dp[W])Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), W = sc.nextInt();
int[] wt = new int[n], val = new int[n];
for (int i = 0; i < n; i++) wt[i] = sc.nextInt();
for (int i = 0; i < n; i++) val[i] = sc.nextInt();
long[] dp = new long[W + 1];
for (int i = 0; i < n; i++)
for (int w = W; w >= wt[i]; w--) dp[w] = Math.max(dp[w], dp[w - wt[i]] + val[i]);
System.out.println(dp[W]);
}
}