POJ 3260 The Fewest Coins

题目链接：POJ-3260

题意是一个人买东西，有n种纸币，面额为v[i]，数量为c[i]。同时售货员也有这些纸币，数量为无限。要买价值为t的东西，希望给“钱用的纸币数和着钱用的纸币数的和”最少。

思路很显然是完全背包和多重背包各处理售货员和这位老哥。这个题给出所有v[i]<=120，这一点很有迷惑性。

一开始我的做法是把上界设成t+120，但是发现这样的做法是不多的。网上给出的做法是设上界为maxv*maxv+t。证明过程如下：

要凑足（大于等于）价格T的商品且硬币数最少，最多只能多给max_v * max_v的金额（其中max_v为硬币的最大面值），称此上界为W。为什么会有这么紧的上界呢，假设存在一种最优支付方案，给了多于t + max_v * max_v的钱，那么商店就会找回多于max_v * max_v的钱，这些硬币的个数大于max_v。设这些硬币的面值分别为a_i，根据鸽笼原理的应用，硬币序列中存在至少两个子序列，这两个子序列的和分别都能被max_v整除。如果我们直接用长度更小的那个子序列换算为面值为max_v的硬币某整数个，再去替换母序列就能用更少的硬币买到商品，形成矛盾。

关于整除更详细的证明如下，尝试构造这样的子序列。长度为max_v+x的母序列至少可以找两个不同的长度为max_v的子序列出来，按照《组合数学》中的证明：

不过其实简单的办法就是把上界设大一点。

代码如下：

#include<cstdio>
#include<set>
#include<map>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;

int n,t;
int v[110],c[110];
int f[24400],g[24400];
int maxn;
void init()
{
    memset(f,0x3f3f3f3f,sizeof(f));
    memset(g,0x3f3f3f3f,sizeof(g));
    g[0]=f[0]=0;
}
int main()
{
#ifdef LOCAL
    freopen("in.txt","r",stdin);
#endif
    while(scanf("%d%d",&n,&t)!=EOF)
    {
        init();
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&v[i]);
            maxn=max(maxn,v[i]);
        }
        maxn=maxn*maxn+t+1;
        for(int i=1;i<=n;i++) scanf("%d",&c[i]);
        for(int i=1;i<=n;i++)
        {
            int j,cc=c[i];
            for(j=1;j<=cc;j*=2)
            {
                int V=v[i]*j,C=j;
                for(int k=maxn;k>=V;k--)
                    f[k]=min(f[k],f[k-V]+C);
                cc-=j;
            }
            if(cc)
            {
                j=cc;
                int V=v[i]*j, C=j;
                for(int k=maxn;k>=V;k--)
                    f[k]=min(f[k],f[k-V]+C);
            }
        }
        for(int i=1;i<=n;i++)
            for(int j=v[i];j<=maxn;j++)
                g[j]=min(g[j],g[j-v[i]]+1);
        int ans=0x3f3f3f;
        for(int i=t;i<=maxn;i++)
            ans=min(ans,f[i]+g[i-t]);
        if(ans>=0x3f3f3f) printf("-1\n");
        else printf("%d\n",ans);
    }
    return 0;
}

POJ 3260 The Fewest Coins

推荐阅读