0

我在 Python 中实现了一个二叉决策树来解决一个非常标准的背包问题：有一个对象集合，每个对象都有一个关联的权重和值，并且必须选择对象以最大化值，受权重约束。

我知道如何返回最大值，但我正在努力寻找一种聪明的方法来返回产生最大值的对象的身份。

现在，我正在创建一个“字符串向量”，可以说，“1”和“0”代表选择打包或不打包某个对象。字符串向量中的第一个“1”或“0”表示为与对象列表中的第一个对象对应的对象做出的决定，依此类推。

有一个更好的方法吗？

我写的代码：

def knapsack(weightList, valueList, availableWeight, index):
    if index == 0:
        if weightList[index] <= availableWeight:
            return valueList[index], '1'
        else:
            return 0, '0'
    else:
        reject, rVector = knapsack(weightList, valueList, availableWeight, index - 1)
        rVector += "0"
        if weightList[index] <= availableWeight:
            take, tVector = knapsack(weightList, valueList, availableWeight - weightList[index], index - 1)
            take += valueList[index]
            tVector += "1"
        else:
            take = -1

        if take > reject:
            return take, tVector
        else:
            return reject, rVector

weightList = [1, 2, 6, 5, 8, 3, 7, 2, 4, 7, 1]
valueList = [2, 5, 4, 6, 7, 8, 2, 4, 5, 6, 8]
availableWeight = 5
index = len(weightList) - 1

maxValue, vector = knapsack(weightList, valueList, availableWeight, index)
print maxValue
print vector

输出是：

18
10000100001
4

1 回答 1

0

如果字符串最终包含大部分“0”和一些“1”，那么最好返回一个 Python 集合对象。一旦你得到一个集合的结果，它仍然可以让你有效地决定一个索引是否在集合中——因此首先使用一串标志几乎没有优势。

请注意，集合是可变的，如果在您的算法中实施不正确，可能会造成混乱。我建议更喜欢“frozenset”而不是“set”。

于 2012-09-17T09:42:26.167 回答