0

かなり標準的なナップサック問題を解決するために、Pythonで二分決定木を実装しました。それぞれに重みと値が関連付けられたオブジェクトのコレクションがあり、重みの制約に従って、値を最大化するようにオブジェクトを選択する必要があります。

最大値を返す方法はわかりますが、最大値を生成したオブジェクトのIDを返す賢い方法を見つけるのに苦労しています。

現在、私は「文字列ベクトル」を作成しています。「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セットオブジェクトを返す方がはるかに優れています。結果をセットとして取得した後でも、インデックスがセットに含まれているかどうかを効率的に判断できるため、そもそもフラグの文字列を使用する利点はほとんどありませんでした。

セットは変更可能であることに注意してください。アルゴリズムに正しく実装されていない場合、混乱が生じる可能性があります。「set」よりも「frozenset」を優先することをお勧めします。

于 2012-09-17T09:42:26.167 に答える