825 . 無限背包問題
TopCoder
Description
現在有 $N$ 個物品，第 $i$ 個物品的重量為 $w_i$，價值為 $v_i$。每個物品都有無限多個。
你有一個重量限制為 $W$ 的背包，你希望可以在不超過這個背包重量限制的前提下，盡可能塞入價值總和最高的物品。請問你可以塞入最高的物品總價值是多少？
Input Format
輸入第一行有兩個正整數 $N, W$，代表物品的數量以及背包重量的限制。
第二行有 $N$ 個正整數，第 $i$ 個數字 $w_i$ 代表第 $i$ 個物品的重量。
第三行有 $N$ 個正整數，第 $i$ 個數字 $v_i$ 代表第 $i$ 個物品的價值。
- $1\leq N \leq 1000, 1\leq W\leq 200$
- $1\leq w_i \leq W$
- $1\leq v_i \leq 10^ 9$
Output Format
輸出一行一個整數代表背包可以裝的最大價值總和。
Sample Input 1
3 8
1 2 3
4 5 6
1 2 3
4 5 6
Sample Output 1
32
Sample Input 2
2 10
2 3
5 9
2 3
5 9
Sample Output 2
28
Hints
Problem Source
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~1 | 範例測資 | 0 |
| 2 | 0~13 | 無額外限制 | 100 |