http://acm.hdu.edu.cn/showproblem.php?pid=2602
01背包：用二维数组实现。
c[n][m]表示n种物品，背包容量为m的最大价值。
状态方程为:f(n,m)=max{f(n-1,m), f(n-1,m-w[n])+P(n,m)}这就是书本上写的动态规划方程.
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 24513 Accepted Submission(s): 9911
1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 using namespace std; 5 int c[1010][1010]; 6 int p[2000],w[2000]; 7 int main() 8 { 9 int t,n,m,i,j; 10 cin>>t; 11 while(t--) 12 { 13 memset(p,0,sizeof(p)); 14 memset(w,0,sizeof(w)); 15 memset(c,0,sizeof(c)); 16 cin>>n>>m; 17 for(i=1;i<=n;i++) 18 cin>>p[i]; 19 for(i=1;i<=n;i++) 20 cin>>w[i]; 21 for(i=1;i<n+1;i++) 22 for(j=0;j<m+1;j++) 23 { 24 if(w[i]<=j) 25 { 26 if(p[i]+c[i-1][j-w[i]]>c[i-1][j]) 27 c[i][j]=p[i]+c[i-1][j-w[i]]; 28 else 29 c[i][j]=c[i-1][j]; 30 }else 31 c[i][j]=c[i-1][j]; 32 } 33 printf("%d\n",c[n][m]); 34 35 } 36 return 0; 37 }
原文：http://www.cnblogs.com/cancangood/p/3567696.html