【模板】01背包问题

题目描述:

一个旅行者有一个最多能装$M$公斤的背包，现在有$n$件物品，它们的重量分别是$W_1,W_2,\cdots,W_n$,它们的价值分别为$C_1,C_2,\cdots,C_n$，求旅行者能获得最大总价值。

输入格式:

第一行：两个整数，$N$(物品数量，$N\le100$) 和$M$(背包容量，$M\le1000$) ；

第$2$~$N+1$行：每行二个整数$W_i$，$C_i$，表示每个物品的重量和价值。

输出格式:

仅一行，一个数，表示最大总价值。

样例输入:

(双击复制)

4 10
2 1
3 3
4 5
7 9

样例输出:

(双击复制)

12

时间限制: 1000ms
空间限制: 256MB

---