背包问题(bag)
【题目描述】
有一个容量为W的背包，有N种物品，第i种物品的体积为 Ti ，价值为 Vi 。
对于每种物品，你可以选择是否将它放入背包，放入背包的物品的总体积不能超过 W ，在这个前提下你希望放入背包的物品的总价值最大。
【输入数据】 bag.in
第一行两个数 W ,N，表示背包的容量和物品的数量。
之后N行，每行两个数 Ti ,Vi，表示第i件物品的体积和价值。
【输出数据】 bag.out
输出一个数，放入背包的物品的最大总价值。
【样例】
9 3
7 14
5 9
4 7
16
【数据规模】
| 测试点编号 | N | W |
|---|---|---|
| 1 | 10 | 100 |
| 2 | ||
| 3 | 1000 | 10000 |
| 4 | ||
| 5 | 50 | 10000000 |
| 6 | 70 | |
| 7 | 100 | |
| 8 | 120 | |
| 9 | 150 | 100000000 |
| 10 | 200 |