背包有关问题之硬币找零有关问题
背包问题之硬币找零问题
设有6 种不同面值的硬币，各硬币的面值分别为5 分，1 角，2 角，5 角，1 元，2元。现要用这些面值的硬币来购物和找钱。购物时可以使用的各种面值的硬币个数存于数组Coins[1:6]中，商店里各面值的硬币有足够多。在1次购物中希望使用最少硬币个数。例如，1 次购物需要付款0.55 元，没有5 角的硬币，只好用2*20+10+5 共4 枚硬币来付款。如果付出1 元，找回4 角5 分，同样需要4 枚硬币。但是如果付出1.05 元（1 枚1元和1 枚5分），找回5 角，只需要3 枚硬币。这个方案用的硬币个数最少。
对于给定的各种面值的硬币个数和付款金额，计算使用硬币个数最少的交易方案。
Input：输入数据有若干组，每一行有6 个整数和1 个有2 位小数的实数。分别表示可以使用的各种面值的硬币个数和付款金额。文件以6 个0 结束。
Output：将计算出的最少硬币个数输出。结果应分行输出，每行一个数据。如果不可能完成交易，则输出"impossible"。
Sample Input：
view sourceprint?1 2 4 2 2 1 0 0.95
2 2 4 2 0 1 0 0.55
3 0 0 0 0 0 0
Sample Output：
view sourceprint?1 2
2 3
解题思路：01背包，完全背包。
change[i]表示商店支付面值为i需要的最少硬币个数；
dp[i]表示顾客现有的硬币数支付面值为i需要的最少硬币数；
w为当前要支付的实际面值，若顾客支付面值为k的钱（k>=w），商家找钱k-w,该条件下最少需要的硬币数为dp[k]+change[k-w]，由此推得，最少硬币数为所有符合条件k>=w下最小的dp[k]+change[k-w];
即： ans = min(dp[k]+change[k-w])(k>=w)。
对于change[i],商店里各面值的硬币有足够多，故可用完全背包实现。
对于dp[i],可用混合背包计算，这里我直接拆成01背包来实现（比较暴力，O(∩_∩)O~）。
PS:为减少空间开销，最终化为以5分为单位计算。
view sourceprint?001 #include<stdio.h>
002 #include<string.h>
003
004 const int N = 20000;
005 int change[N];//change[i]为面值为i的钱至少需要的硬币个数
006 int dp[N];//dp[i]为当前拥有的硬币数量条件下表示面值为i的最少硬币个数
007 int value[6] = {1,2,4,10,20,40};//每种硬币对应面值，依次为1，2,4,10,20,40个五分，即5,10,20,50,100,200；
008 int number[6];//对应于当前拥有的每种硬币个数
009
010 void init()//计算change[i]
011 {
012 int i,j;
013 for(i=0;i<N;i++)change[i]=-1;
014 change[0]=0;
015 for(i=0;i<6;i++)
016 {
017 for(j=value[i];j<N;j++)//这里使用完全背包，不能理解的话可参考背包九讲
018 {
019 if(change[j-value[i]]!=-1)
020 {
021 int temp=change[j-value[i]]+1;
022 if(change[j]==-1||temp<change[j])change[j]=temp;
023 }
024 }
025 }
026 }
027 int main()
028 {
029 //freopen("change.in","r",stdin);
030
031 init(); //计算出change[i]
032
033 while(scanf("%d%d%d%d%d%d",&number[0],&number[1],&number[2],&number[3],&number[4],&number[5])!=EOF)
034 {
035 int sum = 0;
036 int kk;
037 for(kk=0;kk<6;kk++)sum+=number[kk];
038 if(sum==0)break;
039 double weight;
040 scanf("%lf",&weight);
041 weight=weight*100;
042 // printf("weight = %lf\n",weight);
043 int w = int(weight+0.0000001);//处理精度问题
044 //printf("%d\n",w);
045
046 if(w%5!=0)//若不能整除，则无法表示
047 {
048 printf("impossible\n");
049 continue;
050 }
051 else
052 w = w/5;
053
054 int i,j;
055 memset(dp,-1,sizeof(dp));
056 dp[0]=0;
057 int bigger = 0;
058 for(i=0;i<6;i++)//计算顾客支付面值i需要的最少硬币数dp[i]
059 {
060 while(number[i]--) //将混合背包拆成01背包做，写水了点。。。
061 {
062 bigger = bigger+value[i];
063 for(j=bigger;j>=value[i];j--)
064 {
065 if(dp[j-value[i]]!=-1)
066 {
067 int temp=dp[j-value[i]]+1;
068 if(dp[j]==-1||temp<dp[j])
069 {
070 dp[j]=temp;
071 }
072 }
073 }
074 }
075 }
076
077 int ans =-1;
078 for(i=w;i<=bigger;i++)//寻找最少硬币组合
079 {
080 if(dp[i]!=-1)
081 {
082 int need = i-w;
083 if(change[need]!=-1)
084 {
085 int temp = dp[i]+change[need];
086 if(ans==-1||ans>temp)ans=temp;
087 }
088 }
089 }
090
091 // for(i=0;i<N;i++)
092 // if(dp[i]!=-1)
093 // printf("dp[%d]=%d\n",i,dp[i]);
094
095 if(ans!=-1)
096 printf("%d\n",ans);
097 else
098 printf("impossible\n");
099 }
100 return 0;
101 }
设有6 种不同面值的硬币，各硬币的面值分别为5 分，1 角，2 角，5 角，1 元，2元。现要用这些面值的硬币来购物和找钱。购物时可以使用的各种面值的硬币个数存于数组Coins[1:6]中，商店里各面值的硬币有足够多。在1次购物中希望使用最少硬币个数。例如，1 次购物需要付款0.55 元，没有5 角的硬币，只好用2*20+10+5 共4 枚硬币来付款。如果付出1 元，找回4 角5 分，同样需要4 枚硬币。但是如果付出1.05 元（1 枚1元和1 枚5分），找回5 角，只需要3 枚硬币。这个方案用的硬币个数最少。
对于给定的各种面值的硬币个数和付款金额，计算使用硬币个数最少的交易方案。
Input：输入数据有若干组，每一行有6 个整数和1 个有2 位小数的实数。分别表示可以使用的各种面值的硬币个数和付款金额。文件以6 个0 结束。
Output：将计算出的最少硬币个数输出。结果应分行输出，每行一个数据。如果不可能完成交易，则输出"impossible"。
Sample Input：
view sourceprint?1 2 4 2 2 1 0 0.95
2 2 4 2 0 1 0 0.55
3 0 0 0 0 0 0
Sample Output：
view sourceprint?1 2
2 3
解题思路：01背包，完全背包。
change[i]表示商店支付面值为i需要的最少硬币个数；
dp[i]表示顾客现有的硬币数支付面值为i需要的最少硬币数；
w为当前要支付的实际面值，若顾客支付面值为k的钱（k>=w），商家找钱k-w,该条件下最少需要的硬币数为dp[k]+change[k-w]，由此推得，最少硬币数为所有符合条件k>=w下最小的dp[k]+change[k-w];
即： ans = min(dp[k]+change[k-w])(k>=w)。
对于change[i],商店里各面值的硬币有足够多，故可用完全背包实现。
对于dp[i],可用混合背包计算，这里我直接拆成01背包来实现（比较暴力，O(∩_∩)O~）。
PS:为减少空间开销，最终化为以5分为单位计算。
view sourceprint?001 #include<stdio.h>
002 #include<string.h>
003
004 const int N = 20000;
005 int change[N];//change[i]为面值为i的钱至少需要的硬币个数
006 int dp[N];//dp[i]为当前拥有的硬币数量条件下表示面值为i的最少硬币个数
007 int value[6] = {1,2,4,10,20,40};//每种硬币对应面值，依次为1，2,4,10,20,40个五分，即5,10,20,50,100,200；
008 int number[6];//对应于当前拥有的每种硬币个数
009
010 void init()//计算change[i]
011 {
012 int i,j;
013 for(i=0;i<N;i++)change[i]=-1;
014 change[0]=0;
015 for(i=0;i<6;i++)
016 {
017 for(j=value[i];j<N;j++)//这里使用完全背包，不能理解的话可参考背包九讲
018 {
019 if(change[j-value[i]]!=-1)
020 {
021 int temp=change[j-value[i]]+1;
022 if(change[j]==-1||temp<change[j])change[j]=temp;
023 }
024 }
025 }
026 }
027 int main()
028 {
029 //freopen("change.in","r",stdin);
030
031 init(); //计算出change[i]
032
033 while(scanf("%d%d%d%d%d%d",&number[0],&number[1],&number[2],&number[3],&number[4],&number[5])!=EOF)
034 {
035 int sum = 0;
036 int kk;
037 for(kk=0;kk<6;kk++)sum+=number[kk];
038 if(sum==0)break;
039 double weight;
040 scanf("%lf",&weight);
041 weight=weight*100;
042 // printf("weight = %lf\n",weight);
043 int w = int(weight+0.0000001);//处理精度问题
044 //printf("%d\n",w);
045
046 if(w%5!=0)//若不能整除，则无法表示
047 {
048 printf("impossible\n");
049 continue;
050 }
051 else
052 w = w/5;
053
054 int i,j;
055 memset(dp,-1,sizeof(dp));
056 dp[0]=0;
057 int bigger = 0;
058 for(i=0;i<6;i++)//计算顾客支付面值i需要的最少硬币数dp[i]
059 {
060 while(number[i]--) //将混合背包拆成01背包做，写水了点。。。
061 {
062 bigger = bigger+value[i];
063 for(j=bigger;j>=value[i];j--)
064 {
065 if(dp[j-value[i]]!=-1)
066 {
067 int temp=dp[j-value[i]]+1;
068 if(dp[j]==-1||temp<dp[j])
069 {
070 dp[j]=temp;
071 }
072 }
073 }
074 }
075 }
076
077 int ans =-1;
078 for(i=w;i<=bigger;i++)//寻找最少硬币组合
079 {
080 if(dp[i]!=-1)
081 {
082 int need = i-w;
083 if(change[need]!=-1)
084 {
085 int temp = dp[i]+change[need];
086 if(ans==-1||ans>temp)ans=temp;
087 }
088 }
089 }
090
091 // for(i=0;i<N;i++)
092 // if(dp[i]!=-1)
093 // printf("dp[%d]=%d\n",i,dp[i]);
094
095 if(ans!=-1)
096 printf("%d\n",ans);
097 else
098 printf("impossible\n");
099 }
100 return 0;
101 }