← 返回 microsoft 的题目列表0/1 Knapsack
类型：online_judge
Given n items, each item may be selected at most once.
Item i has weight weights[i].
Item i has value values[i].
The knapsack has maximum capacity capacity.
Choose a subset of items whose total weight does not exceed capacity, maximizing the total value. Return the maximum achievable value.
Input Format
n capacity
w1 v1
w2 v2
...
wn vn
Output Format
maximum total value
Constraints
1 <= n <= 2000
1 <= capacity <= 10000
1 <= weights[i] <= capacity
0 <= values[i] <= 10^9
Example 1
Input:
3 4
2 3
1 2
3 4
Output:
6
Explanation: Select the items with (weight, value) pairs (1, 2) and (3, 4).
Example 2
Input:
4 7
1 1
3 4
4 5
5 7
Output:
9
Explanation: Select the items with (weight, value) pairs (3, 4) and (4, 5).
Example
Input
3 4
2 3
1 2
3 4
Output
6