有N中物品和一个容量为V的背包，每种物品都有无限件可以使用。第i中物品的费用是c[i]，价值是w[i]。
求将哪些物品放入背包可以使这些物品的费用总和不超过背包容量且价值总和最大。
分析思路
每个物品都是无限件，也就当取第i件物品的时候，有0件、1件、2件。。。。等等多种情况。
令f[i,v]表示前i种物品放入一个容量为v的背包时候 取得的最大价值。动态转移方程为：
dp[i,v]=max{
dp[i-1][v-k*c[i]]+w[i] || 0<=k*c[i] <=v}
#include<stdio.h>
#include<string.h>
int main()
{
int
N,M,c[100],w[100],dp[200][200],dp1[2000];
while (scanf("%d%d",&M,&N)!=EOF)
{
//获取数据
for(int i=1;i<=N;i++)
scanf("%d%d",&c[i],&w[i]);
//数据初始化
for(int j=0;j<=M;j++)
if(j>=c[1]) dp[1][j]=w[1];
else
dp[1][j]=0;
//利用递推公式
for(int i=2;i<=N;i++)
for(int j=0;j<=M;j++)
{
dp[i][j]=dp[i-1][j];
int max_temp=0;
for(int k=0;k<=j/c[i];k++) //这里K从1开始也可以的。因为K=0的情况也被纳入了dp[i][j]=dp[i-1][j]
max_temp=(dp[i-1][j-k*c[i]]+k*w[i])>max_temp?(dp[i-1][j-k*c[i]]+k*w[i]):max_temp;
dp[i][j]=max_temp;
}
printf("%d\n",dp[N][M]);
}
return 0;
}
同样的，这个可以进行改进。使用一维数组的方式。
for i=1....N
for v=0.....V
dp[v]=max{ dp[v] ,
dp[v-c[i]]+w[i]
}
同样的当v<c[i]的时候dp[v]还是原来的没有改变，
这个代码在改进一下就是
for i=1.....N
for v=c[i]......V
dp[v]={ dp[v],dp[v-c[i]]+w[i]
}
完整的实现
memset(dp1,0,sizeof(dp1));
for(int i=1;i<=N;i++)
for(int j=c[i];j<=M;j++)
dp1[j]=dp1[j]>dp1[j-c[i]]+w[i]?dp1[j]:dp1[j-c[i]]+w[i];
printf("%d\n",dp1[M]);
这里第二层循环v的顺序和01背包是相反的。在考虑“加选一件第i种物品”这种策略时，却正需要一个可能已选入第i种物品的子结果f[i][v-c[i]]，所以就可以并且必须采用v=c[i]..V的顺序循环。
所以一定要注意01背包和完全背包的区别。