问题 J: 【提高】简单背包问题
内存限制：64 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：63
解决：44
题目描述
有一个背包能装的重量c(正整数，0≤c≤20000)，同时有n件物品(0≤n≤100)，每件物品有一个重量w(正整数)和一个价值v(正整数)。要求从这n件物品中任取若干件装入背包内，使背包的物品价值最大。(0≤w,v≤100)
输入
第1行：背包最大载重c，物品总数n
第2行到第n+1行：每个物品的重量和价值
第2行到第n+1行：每个物品的重量和价值
输出
一个数字即背包内物品最大价值
样例输入 复制
10 3
4 5
3 4
6 9样例输出 复制
14提示
c=10 n=5
重量w 价值v
第一个物品： 10 5
第二个物品： 1 4
第三个物品： 2 3
第四个物品： 3 2
第五个物品： 4 1
测试数据二：
10 5
2 6
2 3
6 5
5 4
4 6
15
重量w 价值v
第一个物品： 10 5
第二个物品： 1 4
第三个物品： 2 3
第四个物品： 3 2
第五个物品： 4 1
| 重量w | 价值v | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| 10 | 5 | ||||||||||
| 1 | 4 |
|
|
|
|
|
|
|
|
|
|
| 2 | 3 |
|
|
|
|
|
|
|
|
|
|
| 3 | 2 |
|
|
|
|
|
|
|
|
|
|
| 4 | 1 |
|
|
|
|
|
|
|
|
|
|
测试数据二：
10 5
2 6
2 3
6 5
5 4
4 6
15