230. The Knapsack

I'm a slow walker, but I never walk backwards.

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

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

Discussion