Getting everything ready for you…

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

0s

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

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

  1. dp[w] = best value achievable with total weight ≤ w using the items processed so far.
  2. 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]);
    }
}

Solve 0/1 Knapsack online · All practice problems