有n件物品和一个容量为c的背包。第i件物品的重量是w[i]，价值是 v[i]。求解将哪些物品装入背包可使这些物品的重量和不超过背包容量，且价值总和最大。输出总价值。
Sample Input
130 10
54 68
4 58
85 67
1 6
35 64
84 57
7 98
57 75
36 96
72 5
70 3
71 100
69 1
1 2
Sample Onput
333
3
1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 #include<cstring> 5 #include<cstdlib> 6 using namespace std; 7 int g[100][1000]; 8 int main() 9 { 10 int c,n; 11 while(~scanf("%d%d",&c,&n)) 12 { 13 int i,j,w,v; 14 scanf("%d%d",&w,&v); 15 for(i=1;i<=w;i++) 16 g[1][i]=0; 17 for(i=w;i<=c;i++) 18 g[1][i]=v; 19 for(i=2;i<=n;i++) 20 { 21 scanf("%d%d",&w,&v); 22 for(j=1;j<=c;j++) 23 { 24 if(j<w) 25 g[i][j]=g[i-1][j]; 26 else 27 g[i][j]=max(g[i-1][j-w]+v,g[i-1][j]); 28 } 29 } 30 printf("%d\n",g[n][c]); 31 } 32 return 0; 33 }
原文：http://www.cnblogs.com/xuesen1995/p/4117688.html
