关于背包的硬币找零问题

设有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：

2 4 2 2 1 0 0.95
2 4 2 0 1 0 0.55
0 0 0 0 0 0

Sample Output：

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分为单位计算。

#include
#include
const int N = 20000;
int change[N];//change[i]为面值为i的钱至少需要的硬币个数
int dp[N];//dp[i]为当前拥有的硬币数量条件下表示面值为i的最少硬币个数
int value[6] = {1,2,4,10,20,40};//每种硬币对应面值，依次为1，2,4,10,20,40个五分，即5,10,20,50,100,200；
int number[6];//对应于当前拥有的每种硬币个数
void init()//计算change[i]
{
   int i,j;
   for(i=0;i=value[i];j--)
         {
          if(dp[j-value[i]]!=-1)
          {
            int temp=dp[j-value[i]]+1;
            if(dp[j]==-1||temptemp)ans=temp;
      }
     }
    }
   // for(i=0;i												
本文地址：http://www.nowamagic.net/librarys/veda/detail/844，欢迎访问原出处。