knapsack problem, solved in python
Knapsack problem can be described as follows: given n objects, whose weights are w[1], w[2], ..., 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()