最小白的动态归划入门(硬币找零问题)

算法 admin 28℃ 0评论

想找个最简单的动态归划上上手,于是找到这个个人觉得最典型的动态归划问题:硬币找零问题

给一些不同面值的硬币,其中=1,以及数值M。要计算出找M所需要的最少硬币数。

比如我们有硬币<1,5,10,20>,那么如果要找33块钱的话,最少的零钱数是20+10+1+1+1,一共5个硬币。这就是硬币找零问题的简介。

下面给出几种解法:

  1. 穷举法,这种方法虽然比较笨,但在规模较小的时候,也能够解决问题
    <?php
    function coin(){
    	$n = 9;
    	$m = 3;
    
    	$sum = 0;
    	$log = [];
    	for($i=0; $i<=$n; $i++){
    		for($j=0; $j<=$n; $j++){
    			for($k=0; $k<=$n; $k++){
    				$temp = $i+2*$j+3*$k;
    				if(($sum ==0 || $sum>$temp) && $temp==$n){
    					$sum = $i+$j+$k;
    					$log = [$i, $j, $k];
    				}
    			}
    		}
    	}
    
    	echo $sum;
    
    	echo '<br>';
    	echo "<pre>";
    	var_dump($log);
    	echo "</pre>";
    }
    

     

  2. 贪婪法,这里要注意贪婪法会存在一些问题,要注意优化,尤其是是否能够找出最优解
    function coin1(){
    	$n = 9;
    	$m = [7, 3];
    
    	$sum = 0;
    	$log = [];
    
    	foreach($m as $i){
    		while($n>=$i){
    			$n -= $i;
    			$log[] = $i;
    			$sum ++;
    			if($n<$i) break;
    		}
    
    	}
    
    	echo $sum;
    
    	echo '<br>';
    	echo "<pre>";
    	var_dump($log);
    	echo "</pre>";
    }
    

     

  3. 动态规划法, 这里要注意缓存,可以定义个数组来进行优化,缓存已经做过计算的值
    function coin2($n){
    	$m = [1, 2, 3];
    	$sum = 0;
    
    	if($n>1){
    		for($i=1; $i<count($m); $i++){
    			if($n>=$m[$i-1]){
    				$sum = min(coin2($n-$m[$i-1])+1, coin2($n-$m[$i])+1);
    			}
    		}
    	}
    
    	if($n==0){
    		$sum = 0;
    	}
    
    	if($n == 1){
    		$sum = 1;
    	}
    	return $sum;
    }
    
    echo coin2(9);
    

    这里给一个特别优秀全面的分析:

    若要解一个给定问题,我们需要解其不同部分(即子问题),再根据子问题的解以得出原问题的解。

    用O(n)表示找n块所需最少的硬币数。这里可以看到,如果有硬币<1,3,4>,当想要求6块多需要的最少硬币数时O(6) = min{O(5)+1, O(3)+1, O(2)+1}。即我们想要找6块钱,我们只需要找出6-1=5,6-3=3,6-4=2这三种情况哪一种所需硬币数最少即可。因为我们只要在这三个数上加1即可。

    我们可以总结出对于硬币集合,想要找M块钱,则O(M) = min{O(M-a0)+1,……O(M-an)+1}.

    因此动态规划的伪代码如下。

    DP_coin_change(<a0,a1,...an>,M)
      coin_num <- Recurse_coin_change(<a0,a1,...an,M>)
      return coin_num
     
      Re_coin_change(<a0,a1,...an>,M>)
      if M < 0   return error 
      if M = 0   return 0
      if M = 1   return 1
      coin_num <- min{Re_coin_change(<a0,a1,...an>,M-a0)+1, Re_coin_change(<a0,a1,...an>,M-a1)+1,...Re_coin_change(<a0,a1,...an>,M-an+1)}
      return coin_num

    总的来说,动态归划的难点在于找通项公式,这个问题比较好找,有的问题会比较难找,需要大家不断提升。

 

转载请注明:朋克网 » 最小白的动态归划入门(硬币找零问题)

喜欢 (13)
发表我的评论
取消评论
表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址