欧拉工程第31题：Coin sums

题目链接：https://projecteuler.net/problem=31
把200拆成1、2、5、10、20、50、100、200的组合，看有多少种组合方式。
暴力破解，时间有点长

package projecteuler31to40;import java.util.Date;class level31{void solve2(){
   //11秒13毫秒int num=200;int result=0;
// i+2*j+5*a+10*b+20*c+50*d+100*e+200*ffor(int a=0;a<=200;a++){for(int b=0;b<=200;b+=2){for(int c=0;c<=200;c+=5){for(int d=0;d<=200;d+=10){for(int e=0;e<=200;e+=20){for(int f=0;f<=200;f+=50){for(int g=0;g<=200;g+=100){for(int h=0;h<=200;h+=200){if(a+b+c+d+e+f+g+h==200)result+=1;}}}}}}}}System.out.println(result);}void solve(){
   //25秒662毫秒int num=200;int result=0;for(int i=0;i<=200;i++){for(int j=0;j<=100;j++){for(int a=0;a<=40;a++){for(int b=0;b<=20;b++){for(int c=0;c<=10;c++){for(int d=0;d<=4;d++){for(int e=0;e<=2;e++){for(int f=0;f<=1;f++){if(i+2*j+5*a+10*b+20*c+50*d+100*e+200*f==200){result+=1;}}}}}}}}}System.out.println(result);//可以200的一张的}
}
public class Problem31 {public static void main(String[] args){Date beginTime=new Date();new level31().solve();//73682Date endTime=new Date();long Time=endTime.getTime()-beginTime.getTime();System.out.println("Time:"+Time/1000+"秒"+Time%1000+"毫秒");}}

DFS解题

package greedy;
import java.util.*;
public class changeMoney {public void change(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++){change(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;cM.change(money,A,0,result,"");System.out.println(result.size());}
}

73682