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;
}