问题:给定N个物品和一个背包。物品i的重量是weight，其价值为value,背包的容量为capacity。应该如何选择装入背包的物品，使得放入背包的物品价值最大。

代码:

n = 3  # 物品数量
capacity = 30  # 背包的载重量
weight = [20, 15, 15]  # 物品重量
value = [45, 25, 25]  # 物品价值

max_weight = 0  # 最大载重量
max_value = 0  # 最大价值
bag = [0] * 3
bags = []
best_bag = None  # 最佳解


# 冲突检测
def conflict(k):
    global bag, weight, capacity
    # bag内的前k个物品已经超重，则发生冲突
    if sum([y[0] for y in filter(lambda x: x[1] == 1, zip(weight[:k + 1], bag[:k + 1]))]) > capacity:
        return True
    return False


def knapsack(k):
    global bag, max_value, max_weight, best_bag
    if k == n:
        cv = get_value(bag)
        cw = get_weight(bag)
        if cv > max_value:
            max_value = cv
            best_bag = bag[:]
        # 物品价值相同，重量轻的优先
        if cv == max_value and cw < max_weight:
            max_weight = cw
            best_bag = bag[:]
    else:
        for i in [1, 0]:  # 遍历0,1两种状态:选取1,不选取0
            bag[k] = i
            if not conflict(k):
                knapsack(k + 1)


# 计算重量
def get_weight(bag):
    global weight
    return sum([y[0] for y in filter(lambda x: x[1] == 1, zip(weight, bag))])


# 计算价值
def get_value(bag):
    global value
    return sum([y[0] for y in filter(lambda x: x[1] == 1, zip(value, bag))])


if __name__ == '__main__':
    knapsack(0)
    print('背包重量:', weight)
    print('最佳方案:')
    print('选取的物品为:[选取1,不选取0]', best_bag)
    print('总价值:', get_value(best_bag))

运行结果:

背包重量: [20, 15, 15]
最佳方案:
选取的物品为:[选取1,不选取0] [0, 1, 1]
总价值: 50