动态规划-找零钱问题
问题描述
如果我们有面值为1元、3元和5元的硬币若干枚
问题分析
11-5=6，当需要凑齐6元时，最少的硬币数量方案再加一个5元，就是11元的最佳方案。相当于6元方案再加一个五元硬币。
于是可以得出：
dp(0)=0
dp(1)=dp(1-1)+1=1
dp(2)=dp(2-1)+1=2
dp(3)=dp(3-3)+1=1
dp(4)=dp(4-3)+1=2
dp(5)=dp(5-5)+1=1
dp(6)=dp(6-5)+1=2
dp(7)=dp(7-5)+1=3
dp(8)=dp(8-5)+1=2
dp(9)=dp(9-5)+1=3
dp(10)=dp(10-5)+1=2
dp(11)=dp(11-5)+1=3
根据上述等式可以推理出:
dp(n)=dp(n-可用的最大面值) +1
方案一：
采用动态规划，自底向上计算，保留每一个结果。需要计算从1到11每一个金额的最小硬币方案。
代码：
public static void main(String[] args) throws Exception {
int[] types = {1,3,5};
for(int i=0;i<=11;i++)
exchange(i, types);
}
public static void exchange(int money, int[] types) throws Exception {
List<Integer> parValues = Ints.asList(types);
List<Integer> reference = minResolve(money, parValues);
System.out.println("Money: "+money+", Min icon:"+reference.size()+", coins: "+reference);
}
public static List<Integer> minResolve(int money, List<Integer> parValues) throws Exception {
Map<Integer, List<Integer>> result = new HashMap<>();
result.put(0, Collections.emptyList());
// calc the plan from 1 to X.
for(int i = 1; i <= money; i++){
for(int value : parValues){
if(i >= value) {
// read the reference result
int index = i - value;
List<Integer> tmp = result.containsKey(index) ? result.get(index) : Collections.emptyList();
// if the result is not set, or current plan is better than the old one.
if(!result.containsKey(i) || tmp.size() + 1 < result.get(i).size()) {
// clone the last result, then add the current value.
List<Integer> current = new ArrayList<>(tmp);
current.add(value);
// cover the result
result.put(i, current);
}
}
}
}
return result.get(money);
}
结果：
Money: 0, Min icon:0, coins: []
Money: 1, Min icon:1, coins: [1]
Money: 2, Min icon:2, coins: [1, 1]
Money: 3, Min icon:1, coins: [3]
Money: 4, Min icon:2, coins: [1, 3]
Money: 5, Min icon:1, coins: [5]
Money: 6, Min icon:2, coins: [1, 5]
Money: 7, Min icon:3, coins: [1, 1, 5]
Money: 8, Min icon:2, coins: [3, 5]
Money: 9, Min icon:3, coins: [1, 3, 5]
Money: 10, Min icon:2, coins: [5, 5]
Money: 11, Min icon:3, coins: [1, 5, 5]
方案缺点：
由于方案一采用了动态规划，按照自低向上的方式来计算，必然导致读取多余的节点，而我们要的只有dp(6)+1。因此我们可以换一个思路。
方案2
采用贪心法，每次使用最大面值的硬币，直到凑齐11元。
dp(n)=dp(n-可用的最大面值) + 1
dp(11)
=dp(11-5)+1
=dp(6)+1
=(dp(6-5)+1)+1
=(dp(1)+1)+1
=3
代码：
public static void main(String[] args) throws Exception {
int[] types = {1,3,5};
for(int i=0;i<=11;i++)
exchange(i, types);
}
public static void exchange(int money, int[] types) throws Exception {
// make sure the max value would be tested first everytime.
List<Integer> parValues = Ints.asList(types);
parValues.sort(Collections.reverseOrder());
List<Integer> reference = minResolve(money, parValues);
System.out.println("Money: "+money+", Min icon:"+reference.size()+", coins: "+reference);
}
public static List<Integer> minResolve(int money, List<Integer> parValues) throws Exception {
List<Integer> array = new ArrayList<>();
int count = 0;
// keep changing till it's done.
while(money > 0) {
// use the max value each time.
for(int value : parValues){
count++;
if(money > 0 && money >= value) {
count = 0;
money = money - value;
array.add(value);
break;
}
}
// to avoid endless loop
if(count > (parValues.size())) {
throw new Exception("Can't find out the exchange plan. Plan: "+array);
}
}
return array;
}
结果：
Money: 0, Min icon:0, coins: []
Money: 1, Min icon:1, coins: [1]
Money: 2, Min icon:2, coins: [1, 1]
Money: 3, Min icon:1, coins: [3]
Money: 4, Min icon:2, coins: [3, 1]
Money: 5, Min icon:1, coins: [5]
Money: 6, Min icon:2, coins: [5, 1]
Money: 7, Min icon:3, coins: [5, 1, 1]
Money: 8, Min icon:2, coins: [5, 3]
Money: 9, Min icon:3, coins: [5, 3, 1]
Money: 10, Min icon:2, coins: [5, 5]
Money: 11, Min icon:3, coins: [5, 5, 1]
方案缺点：
这种方式只适用于无论剩余多少钱没被兑换，都有对应硬币面值可以使用。否则无法通过每次选取可用最大值来获得答案。
如：有11块需要找零，硬币面值为2,3,5
运行代码时就会报错
Exception in thread “main” java.lang.Exception: Can’t find out the exchange plan. Plan: [5, 5]
从错误提示中我们可以看到，当前的方案已经选了两个5块硬币，接下来无论选择哪个面值的硬币都无法得出答案。正确的答案应该是3,3,3,2。而这是无法通过贪心法来解答的。
总结
从上述两个方案中我们可以得知：
- 使用动态规划可以将同一个问题分解成n个子问题。对每一个子问题只解一次，而后将解保存，在以后尽可能多地利用这些子问题的解。最后合并解得到答案。
- 贪心法每次做出局部最优解，而不考虑以后的状态。只能在“问题的一个整体最优解，是从贪心选择开始”的情况下才能得出（最佳）答案。