时间限制: 1000 ms 内存限制: 65536 KB
【题目描述】
经典0—1背包问题,有n个物品，编号为i的物品的重量为w[i]，价值为c[i]，现在要从这些物品中选一些物品装到一个容量为m的背包中，使得背包内物体在总重量不超过m的前提下价值尽量大。
【输入】
第1行:两个整数，n(物品数量，n≤3500)和m(背包容量,m≤12880)。
第2..n+1行：：每行二个整数w[i]，c[i]，表示每个物品的重量和价值。
【输出】
仅一行，一个数，表示最大总价值。
【输入样例】
4 6
1 4
2 6
3 12
2 7
【输出样例】
23
1. #include <iostream> 2. #include <cstdio> 3. #include <cstring> 4. #include <algorithm> 5. using namespace std; 6. int f[12900]; 7. int n,m,w,c; 8. int main(int argc, char *argv[]) 9. { 10. scanf("%d %d",&n,&m); 11. for(int i=1;i<=n;i++){ 12. scanf("%d %d",&w,&c); 13. for(int j=m;j>=w;j--) 14. f[j]=max(f[j],f[j-w]+c); 15. } 16. printf("%d\n",f[m]); 17. return 0; 18. }
