hdu1114 & poj1384 完全背包

问题描述：有N种物品和一个容量为V的背包，每种物品有无限件。第i种物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大（或最小）。

按照0-1背包的思路写出状态转移方程：
f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k*c[i]<=v}

优化后的状态转移方程：
f[i][v]=max{f[i-1][v],f[i][v-c[i]]+w[i]}

实现方法：

for i=1..N
for v=0..V
f[v]=max{f[v],f[v-cost]+weight}

[cpp]
#include<stdio.h>
#include<string.h>
#define min(a,b) a<b?a:b
const int INF=999999999;
int c[505],w[505],f[10000];
int main()
{
    int i,j,T,E,F,V,N;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&E,&F);
        V=F-E;
        scanf("%d",&N);
        for(i=0;i<N;i++) scanf("%d%d",&w[i],&c[i]);
        for(f[0]=0,i=1;i<=V;i++) f[i]=INF; //要求恰好装满背包且求最小价值，注意初始化
        for(i=0;i<N;i++){ //主循环,确定物品种类数i(即前i种)
            for(j=c[i];j<=V;j++){ //物品数一定，改变背包容量，注意起止范围
                f[j]=min(f[j],f[j-c[i]]+w[i]);
            }
        }
        if(f[V]!=INF)
            printf("The minimum amount of money in the piggy-bank is %d.\n",f[V]);
        else printf("This is impossible.\n");
    }
    return 0;
}

#include<stdio.h>
#include<string.h>
#define min(a,b) a<b?a:b
const int INF=999999999;
int c[505],w[505],f[10000];
int main()
{
int i,j,T,E,F,V,N;
scanf("%d",&T);
while(T--){
  scanf("%d%d",&E,&F);
  V=F-E;
  scanf("%d",&N);
  for(i=0;i<N;i++) scanf("%d%d",&w[i],&c[i]);
  for(f[0]=0,i=1;i<=V;i++) f[i]=INF; //要求恰好装满背包且求最小价值，注意初始化
  for(i=0;i<N;i++){ //主循环,确定物品种类数i(即前i种)
   for(j=c[i];j<=V;j++){ //物品数一定，改变背包容量，注意起止范围
    f[j]=min(f[j],f[j-c[i]]+w[i]);
   }
  }
  if(f[V]!=INF)
   printf("The minimum amount of money in the piggy-bank is %d.\n",f[V]);
  else printf("This is impossible.\n");
}
return 0;
}

补充：软件开发 , C++ ,