Chinaunix首页 | 论坛 | 博客
  • 博客访问: 978209
  • 博文数量: 102
  • 博客积分: 10120
  • 博客等级: 上将
  • 技术积分: 2754
  • 用 户 组: 普通用户
  • 注册时间: 2006-09-13 23:00
文章分类

全部博文(102)

文章存档

2011年(6)

2010年(55)

2009年(16)

2008年(25)

分类: Python/Ruby

2008-10-12 00:04:10

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()

阅读(1173) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~