酒店设计网站推荐,百度移动开放平台,discuz最新模板,企业名录大全查询找零的两种问题
硬币找零问题#xff0c;有两种。一种用贪心解决#xff0c;一种用动态规划解决。 问题1#xff1a;假设我们有 v1#xff0c;v2#xff0c;……#xff0c;vn#xff08;单位是元#xff09;这些币值的硬币#xff0c;它们的张数分别是 c1、c2、…, …找零的两种问题
硬币找零问题有两种。一种用贪心解决一种用动态规划解决。 问题1假设我们有 v1v2……vn单位是元这些币值的硬币它们的张数分别是 c1、c2、…, cn。我们现在要用这些钱来找零 w元最少要用多少张纸币呢
问题2假设我们有几种不同币值的硬币 v1v2……vn单位是元。如果我们要支付 w 元求最少需要多少个硬币。比如我们有 3 种不同的硬币1 元、3 元、5 元我们要支付 9 元最少需要 3 个硬币3 个 3 元的硬币。
问题1有一个限制条件是不同面额的硬币的张数是有限制的而问题2中没有这个限制。
问题1解决用贪心。选择小于w的面值最大的硬币来付钱。
问题2解决用动态规划。至于为什么不用贪心我也不大明白。接下来重点描述问题2的解决方法。
回溯法解决问题2
回溯法1
因为多次用了回溯法所以很自然想到每次决定一种硬币使用一种数量会产生什么状态。 例如w9 在第0阶段我可以决定1元使用0张产生一种状态支付0元1元使用1张产生一种状态支付1元1元使用2张产生一种状态支付2元… 在第1阶段我可以决定3元使用0张基于上一步的状态产生新的状态支付0、1、2…元使用1张基于上一步的状态产生新的状态13、23… 当支付金额等于9的时候比较最少使用了多少个硬币。
public class CoinChange {//钱币种类private int[] coins new int[]{1,3,5};private int n coins.length;//总金额private int total 9;private int minCount Integer.MAX_VALUE;private void f (int i,int coinCount, int sum){if(sumtotal){minCount Math.min(minCount,coinCount);return;}if(sumtotal){return;}if(in){return;}int maxCount (total - sum)/coins[i];System.out.println(maxCount);for(int j0;jmaxCount;j){f(i1,coinCountj,sumcoins[i]*j);}}public int findCoinCount(){f(0,0,0);return minCount;}}回溯法2
我们还可以换一种思路。我们按照支付金额分阶段。 我们硬币种类有1 元、3 元、5 元。设F(9)表示想要支付9元最少需要几个硬币。F(9)可以从F(9-1)、F(9-3)、F(9-5)三个状态过来分别在这三个状态1选择最低值就是F(9)最少需要支付多少个硬币。
定义状态转移公式 F(S)mini0,1,2...n−1(F(S−ci))1F(S)min_{i0,1,2...n-1}(F(S-c_i))1F(S)mini0,1,2...n−1(F(S−ci))1 ,subject to S−cigt;0S-c_igt;0S−ci0 F(0)0F(0)0F(0)0 F(S)−1F(S)-1F(S)−1,when n0n0n0
上一种回溯中是以每次选择一种硬币作为阶段。这次是每次支付够1元2元3元…n元为阶段。
public class CoinChangeV3 {//钱币种类private int[] coins new int[]{1,3,5};private int n coins.length;//总金额private int total 9;private int f (int total){if(n0) return -1;if(total 0) return 0;int minCount Integer.MAX_VALUE;for(int i0;in;i){if(coins[i]total){int count f(total-coins[i]);minCount Math.min(count,minCount);}}return minCountInteger.MAX_VALUE?-1:minCount1;}public int findCoinCount(){return f(total);}
}备忘录模式 基于上面的回溯画出这样的递归树。树中的每一个节点是一种状态用f(total)表示。total表示当前方法要支付多少元。这感觉不像是以前那种状态我们看到(3). (5)都重复计算了很多次。可以采用备忘录模式减少计算次数。
public class CoinChangeV3 {//钱币种类private int[] coins new int[]{1,3,5};private int n coins.length;//总金额private int total 9;private int f (int total,int[] memory){if(n0) return -1;if(total 0) return 0;if(memory[total] !0) return memory[total];int minCount Integer.MAX_VALUE;for(int i0;in;i){if(coins[i]total){int count f(total-coins[i],memory);minCount Math.min(count,minCount);}}memory[total] minCountInteger.MAX_VALUE?-1:minCount1;return memory[total];}public int findCoinCount(){int[] memory new int[total1];return f(total,memory);}}动态规划
根据动态转移方程计算。 public int findCoinCountDp(){int max total1;int[] dp new int[total1];Arrays.fill(dp,max);dp[0] 0;for(int i1;itotal;i){for(int j0;icoins.length;j){if(coins[j]i){dp[i] Math.min(dp[i],dp[i-coins[j]]1);}}}return dp[total]max?-1:dp[total];}放在最后的一点体会。将问题抽象为多阶段决策问题要分清楚是按照什么分阶段。一般来讲是按照目标指标分阶段。例如支付9元最少需要多少个硬币分阶段为支付8元最少需要多少个硬币支付7元最少需要多少个硬币…。例如从(0,0)走到(n-1,n-1)最少需要多少步目标是(n-1,n-1)前一步可以是(n-1,n-2)或者(n-2,n-1)知道他们的最少步数1就是目标值所以可以按照到达的坐标分阶段。 按照某个指标做分阶段回溯法枚举的时候不一定与此相关。回溯法枚举的时候枚举的是选项。例如不同面值的硬币不同的前进方向。
