PageRank



轉移公告

計劃把 http://blog.hoamon.info/ 文章全部轉移至 http://www.hoamon.info/blog/ 這裡,而本 Blogger 站台的文章近 500 篇,我預計在 2014-12-31 前移轉完畢,完成後 http://blog.hoamon.info/ 將只作代轉服務,一律把舊連結如 http://blog.hoamon.info/index.html 轉成 http://www.hoamon.info/blog/index.html ,敬請舊雨新知互相走告。

新文章只發佈在 http://www.hoamon.info/blog/

何岳峰 敬上

2011年10月1日 星期六

另一種解鋼筋切割組合問題(無界背包問題)的方法(改自 thinker 所提觀念)


#!/usr/bin/env python
# -*- coding: utf8 -*-
""" cut(10, [7, 5, 3, 2]) = cut(3, [7, 5, 3, 2]) + cut(10, [5, 3, 2])
"""
def _plus1(a):
a[0] += 1
return a


def _cache(my_function):
CACHE = {}
def inner_function(*args):
key = str(args[:])
if not CACHE.get(key, None):
CACHE[key] = my_function(*args)
return CACHE[key]

return inner_function


@_cache
def cut(total, sizes):
propers = tuple([sz for sz in sizes if sz <= total])
if len(propers) == 1:
return [[0,]*(len(sizes)-len(propers))+[total/propers[0],],]
elif not propers:
if total < 0:
return []
else:
return [[0,]*len(sizes),]

result1 = [_plus1(a) for a in cut(total-sizes[0], sizes)]
result2 = [[0, ]+a for a in cut(total, sizes[1:])]
return result1 + result2


if __name__ == '__main__':
from time import time

bar = 10
sizes = [7, 5, 3, 2]

t0 = time()
answer = cut(bar, sizes)
print time() - t0

print 'count: %s'%len(answer)
#for a in answer:
# print a, sum([j*sizes[i] for i, j in enumerate(a)])


其計算邏輯是 cut(10, [7, 5, 3, 2]) = cut(3, [7, 5, 3, 2]) + cut(10, [5, 3, 2]) ,這觀念從 Thinker 那邊學來的,它用在計算 cut(10, [7, 5, 3, 2]) 的組合數有多少時,非常非常快,不過,我在擴充至求組合數有那些時,這方法的速度就比不上 cut(10, [7, 5, 3, 2]) = (cut(10, [5, 3, 2]) 的結果,其元素 0 插入 0) + (cut(3, [5, 3, 2]) 的結果,其元素 0 插入 1) 了。

不曉得是不是我在運算過程中,那裡少了優化?

沒有留言:

張貼留言

Related Posts Plugin for WordPress, Blogger...