题解:[USACO06DEC]最少的硬币The Fewest Coins

解法：多重背包+完全背包。
思路：约翰能对各种硬币使用的次数是有限的，于是对约翰做多重背包。而老板对各种硬币的使用次数是无限的，于是对老板做完全背包。然后在min出最小的答案。


Code:

#include<math.h>
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#define maxn 101000
#define INF 1000000000
using namespace std;
int c[110],v[110];
int f[maxn],g[maxn];
int main() {
    int n,t,i,j,k,ans;
    scanf("%d%d",&n,&t);
    int sum=0,mx=0;
    for (i=1; i<=n; i++)scanf("%d",&v[i]);
    for (i=1; i<=n; i++) {
        scanf("%d",&c[i]);
        sum+=c[i]*v[i];  //求John带的钱的总值
        mx=max(mx,v[i]*v[i]);  //根据某某原理，必然有若干个货币组合起来是v_max的倍数，且不大于v_max^2
    }//t+mx即为找钱的上限
    if (sum<t) {printf("-1\n");    return 0;}
    //John带的钱还买不起要买的东西，自然没有解决方案，故直接输出-1并结束程序
    memset(g,63,sizeof(g));
    memset(f,63,sizeof(f));
    g[0]=0;
    f[0]=0;
    for (i=1; i<=n; i++)
        for (j=v[i]; j<=t+mx; j++)
            g[j]=min(g[j],g[j-v[i]]+1); //老板找j元时要花的最少纸币数量
    for (i=1; i<=n; i++) {
        for (j=1; (j=j*v[i])!=0; k--)
            f[k]=min(f[k],f[k-j*v[i]]+j);  //John花k元时要用的最少纸币数量。
        c[i]-=j;
    }
    if (c[i])
        for (k=t+mx; k>=c[i]*v[i]; k--)
            f[k]=min(f[k],f[k-c[i]*v[i]]+c[i]);  //同上
    ans=INF;
    for (i=t; i<=t+mx; i++)ans=min(f[i]+g[i-t],ans);
    printf("%d\n",ans==INF?-1:ans);
    return 0;
}

点我回到主页