首页 > 代码库 > POJ-3260 The Fewest Coins
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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。