The 0/1 knapsack – Algorithms Exercise with Solution

A bag can carry total weight W. There are n items, each with a weight and a value, and each can be taken at most once, whole. What is the largest total value that fits in the bag?

What to build

A dynamic program for the 0/1 knapsack.

Requirements

Let dp[i][c] be the best value from the first i items with capacity c.
Choose the better of leaving item i - 1 and taking it, when it fits.
Print dp[n][W].

Input

The first line has n and W (1 ≤ n ≤ 50, 0 ≤ W ≤ 1000). Each of the next n lines has an item's weight and value (1 ≤ weight ≤ 1000, 0 ≤ value ≤ 1000).

Output

The largest total value.

Constraints

1 ≤ n ≤ 50, 0 ≤ W ≤ 1000, 1 ≤ weight ≤ 1000 and 0 ≤ value ≤ 1000.

Example

Input:

Output:

Why it works

In the best choice for each cell, the last item is either left or taken. Both cases reduce to a smaller cell that is already known.

Examples

Example 1 · Input

Expected output

Example 2 · Input

Expected output

Hints

Hint 1

dp[i][c] = the best value from the first i items with capacity c; row 0 is all zeros.

Hint 2

dp[i][c] is the larger of dp[i-1][c] (leave item i-1) and v + dp[i-1][c - w] (take it, if w <= c).

Hint 3

The answer is dp[n][W].

Solution

Show one correct solution (try it yourself first)

#include <stdio.h>

int dp[51][1001];

int main(void) {
    int n, W;
    int w[50], v[50];
    scanf("%d %d", &n, &W);
    for (int i = 0; i < n; i++) scanf("%d %d", &w[i], &v[i]);
    for (int i = 1; i <= n; i++) {
        for (int c = 0; c <= W; c++) {
            dp[i][c] = dp[i - 1][c];
            if (w[i - 1] <= c && v[i - 1] + dp[i - 1][c - w[i - 1]] > dp[i][c])
                dp[i][c] = v[i - 1] + dp[i - 1][c - w[i - 1]];
        }
    }
    printf("%d\n", dp[n][W]);
    return 0;
}

Lesson: Knapsack and longest common subsequence →