算法.动态规划.最少钱币数问题(Java,递归)

2022/2/22 14:53:45

本文主要是介绍算法.动态规划.最少钱币数问题(Java,递归),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

问题

有11,5,1 三种币值
要凑15块钱
问题:求 钱的张数最小

贪婪法

1. 贪婪法:先用最大的,然后依次,最后用1块做填补
- 如果W比任何一张币值大,且一定可以补够,比如有1块就可以
- 特例:
1. w没有币值大
2. 比如:11,5,3  选11 就凑不够15块,也就是说  先选最大币值未必能拼够
3. 贪婪算法 一般情况下都不是最优解, 只有大面值可以覆盖所有小面值,这种方案才能得到最优解,比如:100,50,10,5,1就可以

动态规划法

动态规划方法
拼凑15块钱,需要最小的钱的张数,称为F(15)
那么:
		F(15) = Min( F(15-11) + 1, F(15-5) + 1, F(15-1) + 1 )
			  = Min( F(4) , F(10) , F(14) ) + 1

		F(10) = Min( F(10-11) + 1, F(10-5) + 1, F(10-1) + 1)
			  = Min( F(-1) , F(5) , F(9) )+ 1
			  = Min( F(5) , F(9) )+ 1
			  = Min( 1 , F(9) )+ 1
说明:
F(4)+1 : 用了一张11块币值,剩余需要凑4块的钱的张数
F(5) : 凑跟币值一样的钱数,当然是直接使用一张5块的就算完事
F(10): 凑10块 可以选:5,也可以选1块。 这个还按照贪婪从大到小,当然还需要比对。
	- 优化点:咱看到5的下一级只需要取5块,2张就完事。 就没必要:5+1+1+1+1+1 直到最后

类似问题:
1. 第n个元素的值:F(n) = F(n-2) + (n-1)
	- n=1,2为2,3
2. 导航问题:假设A-Z导航,A后两条出口B,C
	- Min(a,z) = Min( (A-B) + Min(B,Z) ,(A-C) + Min(C,Z) )

编码:递归,这类问题用递归 跟问题分析很对应

代码(Java)

	
	@Test
	public void test1(){
		// 有11,5,1 三种币值
		int [] currencyValues =new int[]{11,5,1};
		// 要凑15块钱
		int w = 15; 
		// 问题:求 钱的张数最小
		Solution Solution = new Solution();
		Assert.assertEquals(3, Solution.miniNumberOfMoney(currencyValues,w));
		Assert.assertEquals(2, Solution.miniNumberOfMoney(new int[]{11,5,1},6));
		// 这种就是无解场景
		Assert.assertEquals(2, Solution.miniNumberOfMoney(new int[]{11,5,2},6));
	}
	
	/**
	 * 动态规划方法
	 * 拼凑15块钱,需要最小的钱的张数,称为F(15)
	 * 那么:
	 * 		F(15) = Min( F(15-11) + 1, F(15-5) + 1, F(15-1) + 1 )
	 * 			  = Min( F(4) , F(10) , F(14) ) + 1
	 * 
	 * 		F(10) = Min( F(10-11) + 1, F(10-5) + 1, F(10-1) + 1)
	 * 			  = Min( F(-1) , F(5) , F(9) )+ 1
	 * 			  = Min( F(5) , F(9) )+ 1
	 * 			  = Min( 1 , F(9) )+ 1
	 * 说明:
	 * F(4)+1 : 用了一张11块币值,剩余需要凑4块的钱的张数
	 * F(5) : 凑跟币值一样的钱数,当然是直接使用一张5块的就算完事
	 * F(10): 凑10块 可以选:5,也可以选1块。 这个还按照贪婪从大到小,当然还需要比对。
	 * 	- 优化点:咱看到5的下一级只需要取5块,2张就完事。 就没必要:5+1+1+1+1+1 直到最后
	 * 
	 * 类似问题:
	 * 1. 第n个元素的值:F(n) = F(n-2) + (n-1)
	 * 	- n=1,2为2,3
	 * 2. 导航问题:假设A-Z导航,A后两条出口B,C
	 * 	- Min(a,z) = Min( (A-B) + Min(B,Z) ,(A-C) + Min(C,Z) )
	 * 
	 * 编码:递归,这类问题用递归 跟问题分析很对应
	 */
	class Solution {
		public int miniNumberOfMoney(int[] moneys,int w) {
			int miniNum = Integer.MAX_VALUE;
			int tempMiniNum = 0;
			for(int i = 0 ; i < moneys.length ; i++){
				if(moneys[i] > w){
					// 拼凑的钱直接比当前币值小,比如拼凑99块,100面值就直接过了。
					continue;
				}else if(moneys[i] == w){
					// 拼凑的钱 跟 比当前币值相等,那么最新少的就是一张
					tempMiniNum = 1;
				}else if(moneys[i] < w){
					tempMiniNum = miniNumberOfMoney(moneys,w - moneys[i]) + 1;
				}
				
				// 如果这种币值的钱张数 比较少就记录
				if(tempMiniNum < miniNum){
					miniNum = tempMiniNum;
				}
			}
			
			return miniNum;
		}
	}

end



这篇关于算法.动态规划.最少钱币数问题(Java,递归)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程