iT邦幫忙

1

錢幣的組合

演算法挑戰,假設某國有1到30元各不同的錢幣
問題一:
如果要組成27元,請問有幾種組合方式(非排列)
問題二:
如果要組成37元,請問有幾種組合方式(非排列)

kradark iT邦好手 1 級 ‧ 2012-03-30 23:26:14 檢舉
可以用排列組合!
也可以用dynamic programming!

1 個回答

12
wiseguy
iT邦超人 1 級 ‧ 2012-03-30 15:05:22
最佳解答

問題一:3010 種
問題二:21607 種
以下是 php 程式:

<pre class="c" name="code">$kind=0;
ccc(30,27);
echo "27 kind={$kind}\n";
$kind=0;
ccc(30,37);
echo "37 kind={$kind}\n";

function ccc($max, $value)
{
	global $kind;

	if ($max > 0 && $value > 0)
	{
		$a = $value % $max;
		$b = (int)floor($value / $max);

		if ($max > 1 && $a > 0)
			ccc($max-1, $a);
		else
			$kind++;

		for ($i=$b-1; $i>=0; $i--)
		{
	        $d[$max] = $i;
			ccc($max-1, $value-($i*$max));
		}
	}
}
看更多先前的回應...收起先前的回應...
120131511 iT邦研究生 4 級 ‧ 2012-03-30 16:07:18 檢舉

if ($max > 0 && $value > 0)
{

您的算法好像變成排列,而非組合
如1-3元錢幣要算3元有幾總組合
其組合有
111
12
3
三種,但您的演算法會有6種,變成排列了。

wiseguy iT邦超人 1 級 ‧ 2012-03-30 16:39:52 檢舉

樓主有 run 我的程式嗎?
ccc(3,3) 是 3 種沒錯啊。

php.exe -n ccc.php
3元幣=1個
2元幣=1個, 1元幣=1個
1元幣=3個
total=3

120131511 iT邦研究生 4 級 ‧ 2012-03-31 01:12:38 檢舉

抱歉 $kind++ 沒歸零,所以驗證有誤

120131511 iT邦研究生 4 級 ‧ 2012-03-31 02:04:31 檢舉

是否有其他演算法,如樹狀或統計函數,讓執行效率提高?

kradark iT邦好手 1 級 ‧ 2012-03-31 09:35:20 檢舉

dynamic programming

wiseguy iT邦超人 1 級 ‧ 2012-03-31 20:24:46 檢舉

沒錯,用 dp 可以加快百倍以上的速度,樓主可以試試將小弟的 function 改為 dp 版本,即可知效果。

wiseguy iT邦超人 1 級 ‧ 2012-03-31 22:22:45 檢舉

我自己以 dp 改寫後,測試 ccc(30,27)到ccc(30,77) 的結果。
原始函式的時間遞增得相當快,而動態規劃則變動很小。

<pre class="c" name="code">ccc(30, 27)原始函式:quantity=3010  time:0.01195502281189
ccc(30, 27)動態規劃:quantity=3010  time:0.0011961460113525

ccc(30, 37)原始函式:quantity=21607  time:0.09086799621582
ccc(30, 37)動態規劃:quantity=21607  time:0.001121997833252

ccc(30, 47)原始函式:quantity=123839  time:0.54752492904663
ccc(30, 47)動態規劃:quantity=123839  time:0.0013818740844727

ccc(30, 57)原始函式:quantity=602422  time:2.803258895874
ccc(30, 57)動態規劃:quantity=602422  time:0.0016791820526123

ccc(30, 67)原始函式:quantity=2580573  time:12.635329008102
ccc(30, 67)動態規劃:quantity=2580573  time:0.0019540786743164

ccc(30, 77)原始函式:quantity=9974703  time:51.097416877747
ccc(30, 77)動態規劃:quantity=9974703  time:0.0023171901702881
120131511 iT邦研究生 4 級 ‧ 2012-04-01 02:00:22 檢舉

小弟用C#照 wiseguy大大的函式去跑,
ccc(12, 12)要35秒,
ccc(47, 47)超過30分鐘後都沒反應,只好中止,
還在找瓶頸在哪,原先想說用Threading去跑個別遞迴....
dp是不錯的解決方式
PS.電腦是ASUS B121平板/RAM 4G/OS windows 8 / VS 2010

wiseguy iT邦超人 1 級 ‧ 2012-04-01 09:35:06 檢舉

樓主是不是弄錯了什麼了?我用 php 跑,不管 ccc(12,12) 還是 ccc(47,47) 都不到一秒,C# 怎麼可能比 php 這種 script 語言還慢?我的電腦也只是 Core Duo E7200 2.53GHz + 3GB RAM,平板有差這麼多嗎?驚暈

<pre class="c" name="code">ccc(12, 12)原始函式:quantity=77  time:0.019269943237305
ccc(12, 12)動態規劃:quantity=77  time:0.00022411346435547
ccc(47, 47)原始函式:quantity=124754  time:0.51868987083435
ccc(47, 47)動態規劃:quantity=124754  time:0.0037131309509277
120131511 iT邦研究生 4 級 ‧ 2012-04-01 16:27:21 檢舉

我也覺得很納悶。

120131511 iT邦研究生 4 級 ‧ 2012-04-01 16:39:54 檢舉

抓出兇手了,因一個紀錄顯示變數值的TextBox造成的問題,拿掉後就正常了,
只是時間還有點長ccc(50, 50)跑了21秒,不過比之前要快太多了。

wiseguy iT邦超人 1 級 ‧ 2012-04-01 19:56:36 檢舉

齁~ 原來樓主用 GUI 啊~ 難怪我說奇怪,C# 怎麼可能是這種速度?
這種演算法的東西,用 console 模式寫比較準啦~
要不然光是 GUI 處理就耗掉不少時間了

carl830 iT邦研究生 5 級 ‧ 2012-04-03 01:51:30 檢舉

我覺得加上GUI也不應該那麼慢吧
我用C寫(50, 50)也是瞬間出來 GUI有吃那麼重嗎@@?
複雜度也只有(coin數*目標值)而已吧

是說這題我覺得dp還比較簡單 遞迴我反而還要想0.0"

wiseguy iT邦超人 1 級 ‧ 2012-04-03 10:15:05 檢舉

對啊!加上GUI也不應該那麼慢。別說用 C 了,我用 javascript 在網頁跑遞迴,(50,50)也是瞬間就跑完了。要超過10秒的,至少得算 70 元以上。不過這是不做 dp 的結果。改成 dp 跑 (70,70) 也花不到 0.1 秒。

這種題目用遞迴解,只需不到20行程式就解完了,dp是避免它重覆遞迴已經遞迴過的改善措施。所以小弟不明白 carl830 所言《dp還比較簡單 遞迴我反而還要想》,意思是您不是用遞迴解的嗎?不用遞迴的話,程式碼不少喔?

我要發表回答

立即登入回答