网站建设外包合同模板/一键制作单页网站

题目

假设有1元、2元、5元、10元、20元、50元、100元、200元面额的硬币或者纸币。现在需要N元钱，有多少种零钱组合方式？

解题

DFS比较简单

    public void DFS(int m,int[]A,int start,ArrayList<String>result,String str){if(m == 0){    result.add(str);return;}if(A[start]> m){return;}for(int i = start;i<A.length;i++){DFS(m - A[i],A,i,result,str+ " "+A[i]);}}

如上：

1.判断是否是 0

是，保存

2.是否非法

3.遍历组合可能

projecteuler31验证结果正确

当然这样会有许多重合的子问题，更改为动态规划，定义数组保存中

dp[j] = dp[j] + dp[j -A[i]]; // 面值j的零钱可以写出：j = A[i] + (j - A[i]) 求出所有组合方式就是答案

    public void DP(int money,int[]A){int dp[] = new int[money+1]; // dp[j] 表示 j元钱的零钱的组合方式 dp[0] = 1;for(int i = 0;i<A.length;i++){for(int j = A[i];j<= money;j++){dp[j] = dp[j] + dp[j -A[i]]; // 面值j的零钱可以写出：j = A[i] + (j - A[i]) 求出所有组合方式就是答案
            }}System.out.println(dp[money]);}

 

然而贪心的转不过去，网上只看到使得找零的硬币数量最少的硬币数量，而是找零方式的数量

    public void Greedy(int money,int[] A){int num = 0;for(int i =A.length-1;i>=0;i--){num=num+money/A[i]; //先把面值较大的找了money = money%A[i];}System.out.println(num);}

 

所有程序

package greedy;
import java.util.*;
public class changeMoney {public void DP(int money,int[]A){int dp[] = new int[money+1]; // dp[j] 表示 j元钱的零钱的组合方式 dp[0] = 1;// 初始是 1 才能dp[j] = dp[j] + ** 才能增加for(int i = 0;i<A.length;i++){for(int j = A[i];j<= money;j++){dp[j] = dp[j] + dp[j -A[i]]; // 面值j的零钱可以写出：j = A[i] + (j - A[i]) 求出所有组合方式就是答案
            }}System.out.println(dp[money]);}public void Greedy(int money,int[] A){int num = 0;for(int i =A.length-1;i>=0;i--){num=num+money/A[i]; //先把面值较大的找了money = money%A[i];}System.out.println(num);}public void DFS(int m,int[]A,int start,ArrayList<String>result,String str){if(m == 0){    result.add(str);return;}if(A[start]> m){return;}for(int i = start;i<A.length;i++){DFS(m - A[i],A,i,result,str+ " "+A[i]);}}public static void main(String[] args){changeMoney cM = new changeMoney();int[] A={1,2,5,10,20,50,100,200};ArrayList<String> result = new ArrayList<String>();int money = 200;//73682cM.DFS(money,A,0,result,"");System.out.println(result.size());cM.DP(money, A);//73682cM.Greedy(money, A);//1
    }
}