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