C# 版本 最少金币问题 动态规划 算法

@[TOC](C# 版本 最少金币问题 动态规划 算法)

<hr style=" border:solid; width:100px; height:1px;" color=#000000 size=1">

题目

这是一道经典算法题，题目如下： 题目：有面值为2元，5元，7元面值的硬币，买一本27元的书，用最少的硬币组合刚好付清，问题1：需要几枚硬币。问题2：这几枚硬币都是什么？

<hr style=" border:solid; width:100px; height:1px;" color=#000000 size=1">

一、代码

老样子，先上代码，再做解析：

/*题目：有面值为2元，5元，7元面值的硬币，买一本27元的书，用最少的硬币组合刚好付清，问题1：需要几枚硬币。问题2：这几枚硬币都是什么？*/
    /// <summary>
    /// 用动态规划算法，求最少硬币数量
    /// </summary>
    /// <param name="kind">硬币的种类</param>
    /// <param name="amount">总的价格</param>
    /// <returns>硬币的数量</returns>
    public int RequestMinNum(int[] kind, int amount)
    {
        List<int> kindList = new List<int>();
        //声明长度为amount+1的数组
        int[] memo = new int[amount + 1];
        memo[0] = 0;
        for (int i = 1; i <= amount; i++)
        {
            //默认拼不出来，无穷大
            int min = int.MaxValue;
            int kindNum = 0;
            //循环次数为硬币的种类
            for (int j = 0; j < kind.Length; j++)
            {
                //总的价格要大于硬币的面值，并且小于之前最少硬币数量
                if (i - kind[j] >= 0 && memo[i - kind[j]] < min)
                {
                    min = memo[i - kind[j]] + 1;
                    kindNum = j;
                }
            }

            Debug.Log(string.Format("总价格为{0}元。使用硬币的最少数量是{1}个", i, min == int.MaxValue ? -1 : min));
            //列表中添加数据
            kindList.Add(min != int.MaxValue ? kind[kindNum] : 0);

            int cardIndex = min;
            for (int a = i; cardIndex > 0;)
            {
                if (min == int.MaxValue)
                {
                    cardIndex = 0;
                }
                else
                {
                    //打印出都有哪些面值的币
                    Debug.Log(string.Format("第{0}张牌的面值是{1}元", cardIndex, kindList[a - 1]));
                    cardIndex--;
                    a -= kindList[a - 1];
                }
            }

            memo[i] = min;
        }

        //如果是无穷大就返回-1，表示拼不出来，否则返回最少硬币数
        return memo[amount] == int.MaxValue ? -1 : memo[amount];
    }

二、代码解析

上述代码里的注释很详细，如果还有不明白的地方，继续往下看。

1.确定最后一步

先确定最后一步，一定有最后的一枚硬币，最后一枚硬币的面值肯定是规定的面值其中的一种，我们用数组来存他们，也就是代码中传入的int数组类型的参数int[] kind。

2.化成子问题

确定好了最后一步，那整个大问题就变成了前面的n-1步 + 最后一步 而且子问题的结果一定是最优策略，放在这个案例中就是n-1个币+最后一枚硬币。 前面的n-1步凑得数值一定是27-最后一枚硬币的数值kind[j]

3.最少需要的币的数量

我们声明一个数组

//声明长度为amount+1的数组
        int[] memo = new int[amount + 1];

1.这个数组一共有amount+1个元素，amount是要拼凑的值 2.给数组的第一个元素赋值为0，初始化下。 3.两层for循环的嵌套，第一层for循环是用来遍历数组的所有元素的；第二层for循环是用来遍历硬币的种类的。 4.声明一个int值，用来记录最少硬币的数量，默认是拼不出来的，赋值为无穷大。 5.在遍历硬币种类的时候，其实是在判断最后一个币到底用哪个面值是最合适的，筛选条件是： 要拼凑的数值要大于等于币的面值，并且要小于上一步的硬币数量，只有条件都满足的时候，才可以覆盖之前的最小硬币数。 6.想知道拼凑成amount值的数最少要多少个硬币，只需要输出memo[amount] == int.MaxValue ? -1 : memo[amount];就可以了，如果这个值是无穷大，那么说明用现有的硬币种类拼不出来现在这个数。

4.这几个币的面值都是多少

这个问题是我自己加的问题。 1.分析下需求，首先我们可以知道拼凑的总的钱数的最后一个币的面值，我们先把他们存到list中，如果是无穷大，就用0来代替。 2.接下来就是向前遍历从刚才存的库中找出最后一个币的面值，当然遍历的增量不是i--,而是`-这一次最后一张牌的面值，这个面值可以根据索引直接从之前存的库里面去取。 3.注意下，如果最小硬币数等于无穷大，就不打印了。

for (int a = i; cardIndex > 0;)
            {
                if (min == int.MaxValue)
                {
                    cardIndex = 0;
                }
                else
                {
                    //打印出都有哪些面值的币
                    Debug.Log(string.Format("第{0}张牌的面值是{1}元", cardIndex, kindList[a - 1]));
                    cardIndex--;
                    a -= kindList[a - 1];
                }
            }

总结

欢迎大佬多多来给萌新指正，欢迎大家来共同探讨。 如果各位看官觉得文章有点点帮助，跪求各位给点个“一键三连”，谢啦~

声明一下：本博文章若非特殊注明皆为原创原文链接 https://blog.csdn.net/Wrinkle2017/article/details/118942037 ————————————————————————————————

版权声明

版权声明：本博客为非营利性个人原创 所刊登的所有作品的著作权均为本人所拥有 本人保留所有法定权利,违者必究! 对于需要复制、转载、链接和传播博客文章或内容的 请及时和本博主进行联系 对于经本博主明确授权和许可使用文章及内容的 使用时请注明文章或内容出处并注明网址 转载请附上原文出处链接及本声明