必威体育Betway必威体育官网
当前位置:首页 > IT技术

钱币组合问题(一):(每种硬币不限次数)

时间:2019-10-10 16:15:38来源:IT技术作者:seo实验室小编阅读:86次「手机版」
 

硬币组合

钱币组合问题(一):(每种硬币不限次数)

假设我们有8种不同面值的硬币{1,2,5,10,20,50,100,200},用这些硬币组合够成一个给定的数值n。例如n=200,那么一种可能的组合方式为200 = 3 * 1 + 1*2 + 1*5 + 2*20 + 1 * 50 + 1 * 100. 问总过有多少种可能的组合方式?

思路一:暴力穷举

每种硬币最多为N/coins,当n较小时,可以穷举出,注意本程序需要n>200,否则需要更改if判断的位置。(时间超时)

public static int cb = 0;
	public static void brute(int[] coins,int n){
		//有多少种币就有多少个for,此题共有7种
		for(int i =0;i<=n/coins[0];i++){
			for(int j =0;j<=n/coins[1];j++){
				for(int k =0;k<=n/coins[2];k++){
					for(int l =0;l<=n/coins[3];l++){
						for(int m =0;m<=n/coins[4];m++){
							for(int o =0;o<=n/coins[5];o++){
								for(int p =0;p<=n/coins[6];p++){
									if((coins[0]*i+coins[1]*j+coins[2]*k+coins[3]*l+coins[4]*m+coins[5]*o+coins[6]*p)==n){
										cb++;
										//System.out.println("1 2 5 10 20 50 100 各使用"+i+j+k+l+m+o+p+"种");
									};
								}
							}
						}
					}
				}
			}
		}
	}

思路二:分支限界,深度遍历,去掉大于N的情况,注意每种硬币允许使用多次,且122与212、221属于同一种情况,所以限定每次使用的币种(coins[i])应大于等于上次使用的币种(coins[coinlocation]) (时间超时)

static int cc = 0;	//统计总共的数目
	static int[] sum = {0,0,0,0,0,0,0};//用于打印使用状况
	/**
	 * @param coins 钱币列表
	 * @param n 总金额
	 * @param count 当前金额
	 * @param coinlocation 当前使用币种的下标
	 */
	public static void dfs(int[] coins,int n,int count,int coinlocation){
		if(count==n){
			cc++;
			for(int i =0;i<sum.length;i++){
				System.out.print("使用 "+coins[i]+"元:"+sum[i]+"个,");
			}
			System.out.println();
		}else if(count > n){
			return;
		}else {
			//遍历每一种硬币,允许1 2 2,不允许2,1,2
			for(int i=coinlocation;i<coins.length;i++){
				sum[i]++;
				dfs(coins,n,count+coins[i],i);
				sum[i]--;
			}
		}
	}

思路三:动态规划

设d[i][sum]为使用第i中钱币时达到总金额sum的方案数目所以对于钱币i(coins[i]),可以不使用i、使用一个i、使用两个i......使用sum/coins[i]个i,即个,其中用d[i][0] = 1(只有一种方案,即什么币种也不用)d[0][i] =0(不用任何币种组成任意钱数,没有这种操作)。

public static void dynamic_prommgram(int[] coins,int n){
		int[][] d = new int[coins.length+1][n+1];//length+1表示不适用任何币种、只使用1、只使用1 2 只使用1 2 3......等等,共length+1种情况,且n+1表示总计0、1.....至n元共n+1种情况
		for(int i = 0;i<=coins.length;i++) d[i][0] = 1; 
		for(int i = 1 ;i<=coins.length;i++){//因为d[0][i]是0,所以i从1开始
			for(int sum = 1;sum<=n;sum++){//由于d[i][0]==1,所以j从1开始
				for(int k=0;k<=sum/coins[i-1];k++){//例如,使用面值为1时,对应的coins[]下标是i-1,逻辑上河实际上不是一致的
					d[i][sum] +=d[i-1][sum-k*coins[i-1]];
				}				
			}
		}
		System.out.println(d[coins.length][n]);
	}

当然,程序可以简化为一维数组,二维数组的方式易于理解,但一维数组的方式更为简洁,因为d[i][sum]=ξ’d[i-1][X’]=ξ’ξ’d[i-2][X’’]=...即d[i-1]就是累加求和的中间量,所以可以直接使用一维数组表示:

public static void main(String[] args){
	    long[] d= new long[201];
	    d[0]=1;
	    int[] v={1,2,5,10,20,50,100
	    };
	    for(int i=0;i<7;i++){
	        for(int j=v[i];j<201;j++){
	            d[j]+=d[j-v[i]];	   //相当于     		        	
	        }
	    } 	 
	    System.out.println(200+"的组合方式有"+d[200]+"种");
}

参考博客

1.http://www.cnblogs.com/Python27/archive/2013/09/05/3303721.html

C++

2.http://blog.csdn.net/qq_24871519/article/details/53260687

c++

相关阅读

关于端口最大值65535的问题

今天偶然有人问到端口的范围0-65535;百度了一下说是这个范围。仔细想了一下,这个回答太笼统,0是不是可以做端口?65535是不是包含

以3大电商平台为例,解读电商搭配/组合营销功能

组合促销或者搭配促销属于一种追加销售的营销方式,即在用户购买一件商品后,向他推销与该商品密切相关的其它低价产品。那么在设计组

程序员十大非技术面试问题及策略

社会竞争很残酷、面试其实就是一场表演,企业永远喜欢可以随机应变、聪明的求职者。而不喜欢看似老实、实则笨拙不懂变通的求职者。

superslide 多次点击调用slide()和速度问题

在开发过程中遇到很多大坑,比如css3中transition: 0s;会导致superslide调用参数interTime效果不起作用 <p id="slide" class="slid

解决WMI Provide Host占用CPU过高问题(win10亲测有用)

欢迎访问我的个人博客 http://xiaolongwu.cn/ 一、写在前面的话 打开任务管理器看到WMI Provide Host一直占用比较高的CPU资源,

分享到:

栏目导航

推荐阅读

热门阅读