Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

  1. best[c] = the best value achievable with capacity c.
  2. 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]);
    }
}

Solve Unbounded Knapsack online · All practice problems