694 . 背包問題

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

aacpschool

User's AC Ratio

66.7% (2/3)

Submission's AC Ratio

50.0% (2/4)

Tags

apcsc apcsc-enumerate

Description

有一耐重為 $M$ 的背包和 $N$ 個物品，第 $i$ （$1 \le i \le N$）個物品有其重量 $W$ 和價值 $P$，你可以任意選擇一些物品裝填，每個物品最多只能被裝一次。

請問在重量總和不超過耐重的情況下，所能達到最大價值總和為何？

Input Format

輸入第一行是兩個空白分割的整數 $M, N$，分別代表背包限重和物品數量。

接下來有 $N$ 行兩個以空白分割的整數 $W, P$，分別代表物品重量和物品價值。

輸入保證 $1\le N\le 20$，$1\le M, W, P\le 10^ 8$。

Output Format

輸出一行一個整數代表背包最大可裝下的物品價值。

Sample Input 1

10 3
3 5
4 8
5 2

Sample Output 1

13

Sample Input 2

20 4
5 2
6 7
7 13
9 10

Sample Output 2

23

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~20 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 2
1 1000 524288 65536 1 2
2 1000 524288 65536 2
3 1000 524288 65536 2
4 1000 524288 65536 2
5 1000 524288 65536 2
6 1000 524288 65536 2
7 1000 524288 65536 2
8 1000 524288 65536 2
9 1000 524288 65536 2
10 1000 524288 65536 2
11 1000 524288 65536 2
12 1000 524288 65536 2
13 1000 524288 65536 2
14 1000 524288 65536 2
15 1000 524288 65536 2
16 1000 524288 65536 2
17 1000 524288 65536 2
18 1000 524288 65536 2
19 1000 524288 65536 2
20 1000 524288 65536 2
Submit
Back to Top