最少硬币问题-白红宇

最少硬币问题

阅读量：4153 次

发布时间：2019-05-25

本文共 2758 字，大约阅读时间需要 9 分钟。

给定一些硬币，求给定金额下，最少硬币的组合。

可以看出是背包问题

#include 
   
    #include 
    
     using namespace std;int main(){	int money[7] = {2,1,5,10,20,50,100};	int cash;	int dp[100000];	int num[100000];	//memset(dp,0,sizeof(dp));	dp[0] = 0;	for (int i=1;i<100000;++i)		dp[i] = numeric_limits
     
      ::min();	memset(num,0,sizeof(num));	while (scanf("%d",&cash)!=EOF)	{		for (int i=0;i<7;++i)		{			for (int v=money[i];v<=cash;++v)			{								if(v ==dp[v-money[i]] +money[i])//保证dp[v],当金额为v时，各种组合的和也是v				{					dp[v] = dp[v-money[i]] +money[i];					if(!num[v])						num[v] = num[v-money[i]] + 1;					else						num[v] = min(num[v],num[v-money[i]] + 1);				}			}		}		cout<
      
       <

上面的代码我自己都看不懂了。。。

下面的代码可以看出与背包问题的关联，其中每个硬币的权重为1，求最少硬币的数量也就是求权重之和最小的，其中面值可以看成是体积。但是要求的是必须完全等于给定的面值，如果组合成的值小于面值，则f[n] = max

void multiPacket(int cost,int a[],int Volume,int weight,int backtrace[]) {    for (int v = cost; v <=Volume; ++v) {        if (a[v-cost] == numeric_limits
   
    ::max())            continue;        if(a[v-cost] + weight < a[v]) {            a[v] = a[v-cost] +weight;            backtrace[v] = cost;        }       //a[v] = min(a[v],a[v-cost] + weight);    }}void print(int backtrace[], int acount ) {    if (acount > 0) {        cout<
    
     <<" ";        int rest = acount - backtrace[acount];        if (rest > 0) {            print(backtrace,rest);        }    }}void minChange(int coin[],int n, int acount) {    int a[1000];    int backtrace[1000];//backtrace[n]，在总数为n时，选择的最后一个零钱的面额    a[0] = 0;    for (int i=1; i < 1000;++i) a[i] = numeric_limits
     
      ::max();    for (int i = 0; i < n ;++i)        multiPacket(coin[i],a,acount,1,backtrace);    cout<<"minNum: "<
      
       <<" coins: ";    print(backtrace,acount);}int main() {    int money [] = {25, 21, 10, 5, 1};    minChange(money,5,34);}

在有些情况下是可以用贪心算法计算的，当零钱的种类符合特定的情况，并且零钱充裕

public static int[] MakeChange(int money, int[] changes){    int[] result = new int[changes.Length];    for (int i = 0; i < changes.Length; i++)    {        result[i] = money / changes[i];        money = money % changes[i];        if (money == 0) { break; }    }    return result;}

这是一题比较复杂的题目：

设有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 枚硬币。这个方案用的硬币个数最少。

对于给定的各种面值的硬币个数和付款金额，计算使用硬币个数最少的交易方案。

意思是让客户给出的硬币数量+商店找钱用的硬盘数量的值最少

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],可用混合背包计算

转载地址：http://lfeti.baihongyu.com/

你可能感兴趣的文章