Practice › Dynamic Programming
Unbounded Knapsack
Medium · Dynamic Programming · Asked at Amazon, Microsoft, Google
There are n item types with weight w[i] and value v[i]; you may take any number of copies of each. Print the maximum total value with total weight at most W.
Input
First line: n W. Second line: the weights. Third line: the values.
Output
The maximum value.
Constraints
- 1 ≤ n ≤ 1000
- 1 ≤ W ≤ 1000
- 1 ≤ w[i], v[i] ≤ 1000
best[c] = max over items with w ≤ c of best[c − w] + v. Unlike 0/1 knapsack, loop the capacity upward so an item can be reused.
Example 1
Input
2 3 1 1 2 1
Output
6
Example 2
Input
4 8 1 3 4 5 10 40 50 70
Output
110
Hints
- best[c] = the best value achievable with capacity c.
- For each capacity c from 1 to W, try every item that fits: best[c] = max(best[c], best[c − w] + v). Increasing c allows an item to be reused.
Approach
Because copies are unlimited, the optimal filling of capacity c is "some item + an optimal filling of c − w". Compute best for capacities in increasing order so smaller capacities are final before use. (Equivalently, loop items outside and capacities upward inside — the opposite direction from 0/1 knapsack.)
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> w(n), v(n);
for (auto &x : w) cin >> x;
for (auto &x : v) cin >> x;
vector<long long> best(W + 1, 0);
for (int i = 0; i < n; i++)
for (int c = w[i]; c <= W; c++) best[c] = max(best[c], best[c - w[i]] + v[i]);
cout << best[W] << "\n";
return 0;
}Python solution
import sys
data = list(map(int, sys.stdin.read().split()))
n, W = data[0], data[1]
w, v = data[2 : 2 + n], data[2 + n : 2 + 2 * n]
best = [0] * (W + 1)
for wi, vi in zip(w, v):
for c in range(wi, W + 1):
if best[c - wi] + vi > best[c]:
best[c] = best[c - wi] + vi
print(best[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[] w = new int[n], v = new int[n];
for (int i = 0; i < n; i++) w[i] = sc.nextInt();
for (int i = 0; i < n; i++) v[i] = sc.nextInt();
long[] best = new long[W + 1];
for (int i = 0; i < n; i++)
for (int c = w[i]; c <= W; c++) best[c] = Math.max(best[c], best[c - w[i]] + v[i]);
System.out.println(best[W]);
}
}