阿蒙又出題了

by thinker

關鍵字:

linkname:[阿蒙又出題了] http://hoamon.blogspot.com/2007/03/cmclass_08.html ，這次的問題單純是計算問題。我再次使用 Dyanmic Programming 的技巧，並配合 recursive function 。

同樣的 code ，在使用 linkname:[Dynamic Programming] http://en.wikipedia.org/wiki/Dynamic_programming 之前，和加上 Dynamic Programming 之後，執行時間是 24.1s 對上 0.037s ，相差 650 倍左右。測試時的執行參數為
{{{
bash-2.05b$$ ./bag.py 500 10 7 2 3
}}}
bag.py 是這個程式的檔名。這個問題是典型的 linkname:[bag problem] http://en.wikipedia.org/wiki/Paper_bag_problem ，是教科書上使用 Dynamic Programming 的標準$範例$。

{{{#!python
import sys

def dynamic(func):
    cache = {}
    def wrapper(*args):
        try:
            return cache[args]
        except KeyError:
            cache[args] = func(*args)
            pass
        return cache[args]
    return wrapper

@dynamic
def bag(sizes, total):
    propers = tuple([sz for sz in sizes if sz <= total])
    if not propers:
        if total >= 2:
            return 0
        else:
            return 1
        pass
    
    first = propers[0]
    num = bag(propers, total - first)
    num = num + bag(propers[1:], total)
    return num

total = int(sys.argv[1])
sizes = tuple([int(sz) for sz in sys.argv[2:]])
print bag(sizes, total)
}}}

最後更新時間: 2007-03-09 00:18:25 CST | 引用

查詢:

COMMENTS:

on 2007-12-19 22:46:40 CST

hoamon said ..

在 18 行的 if total >=2 : 的部份。那個 2 應該要是 min(sys.args[1:]) 才對。

on 2007-12-19 22:47:34 CST

hoamon said ..

sorry, 應該是 min(sys.args[2:])

on 2007-12-19 22:54:23 CST

hoamon said ..

上面用的 dynamic 方法可以用在列出所有的組合情形嗎?

on 2011-10-01 15:43:27 CST

hoamon said ..

經過這麼久的時間，我終於把這個計算架構用在求解組合數有那些( http://hoamon.blogspot.com/2011/10/thinker.html )上了。不過，效率比起另一種架構還要慢，不曉得是不是我那裡沒寫好。

on 2011-10-01 22:27:34 CST

Thinker said ..

這和你用來測試的 case 有關。這類技巧通常要在大問題上才會發揮威力，例如 bag 和 item 的數量都很大時。對於小問題，暴力法往往還比較佔上風。例如: 用於 sort 只有 10 個 item 的小數列，使用 bubble sort 可能都比 quick sort 快。問題在於 algorithm 的 overhead 是否能在該問題的規模上，得到補嘗。