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.