换零钱问题如何限制零钱数

  • Z时代
  • 2024-01-10
  • 分类：IT

Q05现金支付就是大整数分解问题.将一个大整数，用指定的小整数进行组合。
Q05中作者先通过一个特定的例子，比如求1000元日元的组合，并且给出了限制，最多兑换的硬币个数不超过15.
<!--more-->

1000日元的组合情况:

/*
    Name: Q05现金支付
    Copyright: 52coder.net
    Author: 52coder
    Date: 04/09/17 23:44
    Description: Q05
*/
#include <stdio.h>
#include <stdlib.h>
int main()
{
    int i,j,k,l;
    int cnt = 0;
    for (i = 0; i <= 2; i++)
    {
        for(j = 0;j <= 10;j++)
        {
            for(k = 0;k <= 20;k++)
            {
                for(l = 0;l <= 100;l++)
                {
                    if((500*i+100*j+50*k+10*l==1000)&&(i+j+k+l)<=15)
                    {
                        cnt += 1;
                    }
                }
            }
        }
    }
    printf("%d\n",cnt);
    return(0);
}

但这种解法缺少扩展性，比如我想要求解5000元的兑换方式等等，或者更改了币值，假如可以兑换1000一张的硬币等。上面的程序就无法正确求解。
递归思路：

图片来源 知乎用户酿泉 第一个回答作者.
这里以6元拆分成 1元 2元 5元 作为例子，递归的思路是是否使用最大面额零钱与否。
例如最开始6元，我如果使用最大面值为5的零钱，那么还有1元钱需要换成零钱，然后再从 1元 2元 5元中去换钱,此例中由于金额较小，所以只用了一次最大金额，如果面值为100，会用到很多次，使用6元，也能反映问题。
右侧分支是最大面值中不包含5元的情况，那么最大零钱只能使用1元和2元。
依次类推递归，递归的终止条件是分支中出现了0或递归到最小零钱.

/*
    Name: Q05现金支付
    Copyright: 52coder.net
    Author: 52coder
    Date: 04/09/17 23:44
    Description: Q05
*/
#include <stdio.h>
#define ARRAY_SIZE(a)   (sizeof(a)/sizeof(a[0]))
#define TOTAL   100
int g_all_coins[] = {50, 25, 10, 5, 1};
#define COIN_NUM ARRAY_SIZE(g_all_coins)
int count(int sz, int coins[], int total)
{
    int t_coins[COIN_NUM] = {0};
    if(total == 0) return 1;
    if(total <= 0) return 0;
    if(sz <= 0) return 0;
    for(int i = 0; i < sz - 1; i++)
    {
        t_coins[i] = coins[i+1];
    }
    return count(sz-1, t_coins, total) + count(sz, coins, total-coins[0]);
}
int main(int argc, char* argv[])
{
    printf("count(%d) = %d\n", TOTAL, count(COIN_NUM, g_all_coins, TOTAL));
    return 0;
}

现在的问题是该如何限制，最大零钱数呢？比如兑换100的零钱不能兑换100个1元，最多零钱个数不能超过15，这里应该用什么条件去限制呢？

回答：

dp 问题可以写成递归, 也可以写成迭代形式,

  1. 迭代的话多一个数组保存当前零钱数即可.

  2. 递归: 要多记录零钱数这个量的话的话, 递归函数中可以加参数, 记录当前所用的总数; 或者用一个全局变量同理1

以上是 换零钱问题如何限制零钱数 的全部内容， 来源链接： utcz.com/p/195010.html

回到顶部