一篇文章解决所有常见“零钱问题”-Java贪心+DP

1. 无限个数的凑零钱问题

我们经常会遇到这种问题（其实在生活中也很常见）：

-----------

例1：

   设有n种不同面值的硬币，现要用这些面值的硬币来找开待凑钱数m，可以使用的各种面值的硬币个数不限。    找出最少需要的硬币个数？

如：有4种硬币，分别是1,2,5,10； 现在需要用最少硬币凑出来目标值：23，怎么做？

------------

很明显，我们一眼就可以看出来，最少4个（2个10,1个2，1个1）.  但是计算机怎么解决呢？ 

以下介绍了两种方法，分别是常见的贪心和动态规划。

1.1 贪心

贪心的思想就是每次只着眼当前，只看局部最优，那么就是先用面值大的，如果target小于面值大的，再考虑小的。

代码如下：

// 每种硬币个数无限 public static int getMinCoin1(int[] money, int target){ int res = 0; for (int i=money.length-1; i>=0;i--){ while (target>=money[i]){ target -= money[i]; res += 1; } } return target==0?res:-1; }

值得注意的是：贪心并不适合所有情况！

贪心算法适合的条件：零钱面值的倍数满足大于等于2倍的关系！！！

【有关不满足2倍关系不能使用贪心的例子】

*********

例2：

硬币面值为{1,2,5,7,10}，若要凑出14，贪心算法结果会是3（10+2+2），但其实应该是2（7+7）.

*********

此时就要考虑使用DP了

1.2 动态规划

其实，无限个数情况下的最少零钱问题，就是一个（最小）完全背包问题。（如果不太了解背包问题的话，建议看一下背包九讲，或者我后边可能会专门针对背包问题写一篇文章。）

下边是两种DP方法求解无限零钱问题。

代码：

// DP解法 - 每种硬币个数无限 public static int getMinCoin3(int[] money, int target){ if(target==0) return 0; if(money==null || money.length==0) return -1; int[] dp = new int[target+1]; Arrays.fill(dp,target+1); dp[0] = 0; for (int i = 0; i < target+1; i++) { for (int j=0;j<money.length && i>=money[j];j++) { dp[i] = Math.min(dp[i],dp[i-money[j]]+1); } // System.out.println(Arrays.toString(dp)); } return dp[target]==target+1?-1:dp[target]; } // DP解法 - 每种硬币个数无限 // 其实是个(最小)完全背包问题 public static int getMinCoin33(int[] money, int target){ if(target==0) return 0; if(money==null || money.length==0) return -1; int[] dp = new int[target+1]; Arrays.fill(dp,target+1); dp[0] = 0; for (int i = 0; i < money.length; i++) { for (int j = money[i]; j <= target; j++) { dp[j] = Math.min(dp[j],dp[j-money[i]]+1); } } // System.out.println(Arrays.toString(dp)); return dp[target]==target+1?-1:dp[target]; }

1.3 小结

（1）可以用贪心的例子 int[] money1 = {1,2,5,10}; （2）不可以用贪心的例子： int[] money2 = {1,2,5,7,10}; System.out.println(getMinCoin1(money2,14)); // 3：error System.out.println(getMinCoin3(money2,14)); // 2 System.out.println(getMinCoin33(money2,14)); // 2

如上例子（2），贪心算法的结果是错误的，用DP，则可以求出正确结果。

 

2. 有限零钱个数的最少零钱问题

-----------

例3：

   设有n种不同面值的硬币，现要用这些面值的硬币来找开待凑钱数m，可以使用的各种面值的硬币又有限个（且各不相同）。    找出最少需要的硬币个数？

如：有4种硬币，分别是1,2,5,10； 分别有【3,2,5,1】个，现在需要用最少硬币凑出来目标值：23，怎么做？

------------

此时显然之前的方法不行了，因为硬币10的个数只有1个。此时应为最少6个（4个5, 1个2, 1个1）.

这种问题怎么用代码解决呢？（如下）

2.1 贪心

有限零钱个数的贪心情况和无限个数其实差别不大，主要是需要增加一个条件“判断该类型的零钱是否用完”。

代码：

// 每种硬币个数有限 public static int getMinCoin2(int[] money, int[] counts, int target){ int res = 0; for (int i=money.length-1; i>=0;i--){ for (int j = 0; j < counts[i] && target>=money[i]; j++) { target -= money[i]; res += 1; } } return target==0?res:-1; }

 

2.2 动态规划

有限零钱个数的凑零钱问题，其实就是一个（最小）多重背包问题。

代码：

// DP解法 - 每种硬币个数有限 // 其实是个(最小)多重背包问题 private static int getMinCoin4(int[] money, int[] counts, int target) { int n = money.length; int[] dp = new int[target+1]; Arrays.fill(dp,target+1); dp[0] = 0; for (int i = 0; i < n; i++) { int w = money[i]; for (int j = target; j >= 0; j--) { for (int k = 1; k<=counts[i] && k*w <= j; k++) { // 个数遍历写在最内层 dp[j] = Math.min(dp[j],dp[j-w*k]+k); } } } return dp[target]; }

 

2.3 小结

（1）可以使用贪心算法的例子：

int[] money1 = {1,2,5,10}; int[] counts = {3,4,2,1}; System.out.println(getMinCoin2(money1,counts,27)); System.out.println(getMinCoin4(money1,counts,27));

（2）不可以使用贪心算法的例子

int[] money2 = {1,2,5,7,10}; int[] counts2 = {1,1,3,2,2}; System.out.println(getMinCoin2(money2,counts2,14)); // -1，error System.out.println(getMinCoin4(money2,counts2,14)); // 2

3. 总结

看到这里，应该不难发现，这两种（有限/无限个数）零钱问题，竟然都可以用背包问题解决！神奇的背包，确实有必要学习一下。

本文介绍的并不太详细，重点在于对比“贪心算法”和“动态规划”，如有不恰当之处，还望见谅。

------

以上均是个人的一些理解，如有错误还望批评指正。