完成时间：2017年8月21日
代码如下：
/* 问题描述： 有一个容量为m(1<=m<=4000000)的背包，有n(1<=n<=16)个物品，每个物品有体积v(1<=v<=2012)和价值w(0<=2012)，现在要你选择一些物品，使得背包所装物品的总价值最大。 Input 有多组测试数据，但是不会超过10组。 对于每组测试数据，第一行是两个整数m和n，表示背包容量的和物品个数。接下来有n行，每行有两个整数，表示一个物品的体积和价值。 输入到文件结束。 Output 对于每组测试数据，输出一行，包含一个整数，为背包能装下物品的最大价值。 Sample Input 10 3 6 9 5 5 5 5 3 2 1 2 2 1 Sample Output 10 3 作者：何知令 完成时间：2017年8月21日 */ #include <stdio.h> int V[100][100]; int n,m;//n为物品数量，m为背包容量 int w[100],v[100]; void FindMax()//动态规划 { int i,j; //填表 for(i=0; i<=n; i++) { for(j=0; j<=m; j++) { if(j<w[i])//包装不进 { V[i][j]=V[i-1][j]; } else//能装 { if(V[i-1][j]>V[i-1][j-w[i]]+v[i])//不装价值大 { V[i][j]=V[i-1][j]; } else//前i-1个物品的最优解与第i个物品的价值之和更大 { V[i][j]=V[i-1][j-w[i]]+v[i]; } } } } printf("%d\n",V[n][m]); } int main() { int i,j; while(~scanf("%d %d",&m,&n)) { for(i=0; i<m; i++) for(j=0; j<m; j++) V[i][j]=0; for(i=0; i<n; i++) scanf("%d %d",&w[i],&v[i]); FindMax(); } return 0; } 知识点总结：动态规划，背包问题学习心得：又是好久没发博客了
