-230. The Knapsack

Task Description

假設有 $n$ 個物件和一個背包。第 $i$ 個物件的重量為 $w_i$，價值為 $v_i$，而背包有總重量限制 $W$。如何選擇物件放入背包中，使得放入背包的物件總重量不超過背包總重量量限制 $W$，且使得放入背包的物件總價值為最大？

Input

輸入第一行為物件個數 $n$ 及背包重量限制 $W$。接下來會有 $n$ 行，每行有兩個數字，分別是第i個物件的重量 $w_i$ 和價值 $v_i$。

Limits

• $0 \lt n \le 20$
• $0 \lt W \le 10000$
• $0 \lt w_i, v_i \le 1000$

Sample input　

5 6
3 1
1 3
2 3
3 5
3 5

Sample output

11

HINT

可以使用遞迴的方法來求答案。如果我們將第一個物件放入背包，結果是不是得到一個跟原來問題很相近的問題? 如果我們不將第一個物件放入背包，結果是不是也得到一個跟原來問題很像的問題？