0/1 Knapsack

Practice this coding question on Coding Gurukul.

Problem statement

Given n items, each with a weight and a value, choose items with maximum total value such that their total weight is at most W. Each item can be selected at most once. Items with the same weight and value are still separate items. You may select no items, giving value 0. The total weight need not equal W exactly. Print the maximum total value. Use 0/1 knapsack dynamic programming in O(n*W) time and O(W) space. Worked example With capacity 5, the items of weights 2 and 3 give value 3+4=7. This is better than taking the weight-4 item with value 5.

Input format

First line: n W. Next n lines: weight value.

Output format

Print the largest attainable total value.

Constraints

1 <= n <= 100; 0 <= W <= 10000; 1 <= weight <= 10000; 1 <= value <= 10^6.

Sample input

3 5
2 3
3 4
4 5

Sample output

7

Sign in to run or submit a solution in C++, Java or Python.