• 博客访问： 965180
• 博文数量： 102
• 博客积分： 10120
• 博客等级： 上将
• 技术积分： 2754
• 用 户 组： 普通用户
• 注册时间： 2006-09-13 23:00

2011年（6）

2010年（55）

2009年（16）

2008年（25）

2008-10-12 00:04:10

Knapsack problem can be described as follows: given n objects, whose weights are w, w, ..., w[n], respectively. There's a knapsack whose maximum capability is W. The question is: how to select objects from the n objects, so that the selected objects can be fitted in the knapsack?

Theoretically, dynamic progamming can solve knapsack problem in polynomial time. Inspired by this conclusion, I developed a proof-of-concept programme in Python, and here it is:

 ```def knapsack(weiList, totalWei):     elmSet = [set()] * (totalWei + 1)     allSet = set(weiList)     for s in range(1, totalWei + 1):         for j in range(s):             revSet = allSet - elmSet[j]             for elm in revSet:                 if (sum(elmSet[j]) + elm == s):                     elmSet[s] = elmSet[j].union([elm])                          return elmSet[totalWei] def knapsackTest():     Weight = [1,3,5,7,9,11,13]     for S in range(sum(Weight) + 1):         kss = knapsack(Weight, S)         if (len(kss)):             assert(sum(kss) == S)             print S, ":", list(kss) if __name__ == '__main__':     knapsackTest()```