694 . 背包問題

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

aacpschool

User's AC Ratio

75.0% (3/4)

Submission's AC Ratio

60.0% (3/5)

Tags

apcsc apcsc-enumerate

Description

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

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

Input Format

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

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

輸入保證 1≤N≤20，1≤M,W,P≤108。

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