poj 3260 The Fewest Coins （多重背包 + 完全背包）

連結：poj 3260

題意：FJ同學去買東西，東西的價值為T，他和賣家都有N種金币，FJ希望交易完成時金币變化最小。

求最少的金币變化數量。FJ的金币個數有限，賣家的金币數目無限。

思路：背包問題，FJ的每種金币個數有限可以看做是多重背包問題，賣家的金币數目無限可以看做是完全背包問題。

設F1[i]為FJ付款為i時的最小金币數，設F2[i]為賣家找錢為i時的最小金币數。

則F1[i+T]+F2[i]就是所求的最小金币變化數量(F1用多重背包求解，F2用完全背包求解)

PS：這裡的背包求得是最小價值，且要恰好裝滿。故初始化數組時應 F[0]=0,F[1~MAXN]=INT_MAX;

#include<stdio.h>
#define INF 9999999
int f1[1000010],f2[1000010],v;
int min(int a,int b)
{
    return a<b?a:b;
}
void zeroone(int cost,int weight,int *f)   //01背包
{
    int i;
    for(i=v;i>=cost;i--)
        f[i]=min(f[i],f[i-cost]+weight);
}
void complete(int cost,int weight,int *f)        //完全背包
{
    int i;
    for(i=cost;i<=v;i++)
        f[i]=min(f[i],f[i-cost]+weight);
}
void multiple(int num,int cost,int weight,int *f)   //多重背包
{
    int k;
    if(num*weight>=v){
        complete(cost,weight,f);
        return ;
    }
    for(k=1;k<num;k*=2){
        zeroone(k*cost,k*weight,f);
        num-=k;
    }
    zeroone(num*cost,num*weight,f);
}
int main()
{
    int i,T,max,n,num[110],c[110],k;
    while(scanf("%d%d",&n,&T)!=EOF){
        max=0;
        for(i=1;i<=n;i++){
            scanf("%d",&c[i]);
            if(c[i]>max)
                max=c[i];
        }
        for(i=1;i<=n;i++)
            scanf("%d",&num[i]);
        v=max*max+T;                     //因為要找錢，v要比T大很多、、、
        f1[0]=f2[0]=0;
        for(i=1;i<=v;i++)
            f1[i]=f2[i]=INF;
        for(i=1;i<=n;i++)
            multiple(num[i],c[i],1,f1);
        for(i=1;i<=n;i++)
            complete(c[i],1,f2);
        k=INF;
        for(i=0;i<=v-T;i++)
            if(f1[i+T]!=INF&&f2[i]!=INF)
                k=min(k,f1[i+T]+f2[i]);
        if(k==INF)
            k=-1;
        printf("%d\n",k);
    }
    return 0;
}