想找个最简单的动态归划上上手,于是找到这个个人觉得最典型的动态归划问题:硬币找零问题
给一些不同面值的硬币,其中=1,以及数值M。要计算出找M所需要的最少硬币数。
比如我们有硬币<1,5,10,20>,那么如果要找33块钱的话,最少的零钱数是20+10+1+1+1,一共5个硬币。这就是硬币找零问题的简介。
下面给出几种解法:
- 穷举法,这种方法虽然比较笨,但在规模较小的时候,也能够解决问题
<?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>"; }
- 贪婪法,这里要注意贪婪法会存在一些问题,要注意优化,尤其是是否能够找出最优解
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>"; }
- 动态规划法, 这里要注意缓存,可以定义个数组来进行优化,缓存已经做过计算的值
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
总的来说,动态归划的难点在于找通项公式,这个问题比较好找,有的问题会比较难找,需要大家不断提升。
转载请注明:朋克网 » 最小白的动态归划入门(硬币找零问题)