0-1リュックサック問題——遡及法解【Python】

遡及法は0-1リュックサックの問題を解く:
質問:リュックサックの大きさw、物品の個数n、各物品の重量と価値はそれぞれw[i]とv[i]に対応して、リュックサックの中に入れる物品の総価値が最大であることを求めます.
遡及法の核心:入ることができれば進むが、入れなければ変えるが、変えられなければ退く.(条件深さ優先で検索し、あるステップを検索した場合、最適でないか目標に達していない場合は、一歩下がって再選択)
注意:理論的には、遡及法は1本のツリー上でグローバル検索を行いますが、すべての状況がグローバルに考慮する必要はありません.結局、それは効率が低すぎて、制約+限界を通じて多くの不要な検索を減らすことができます.
本問題を解決する考え方:0/1シーケンスを用いて物品の入れ状況を表す.検索を1本の二叉木と見なし、二叉木のi階はi番目の物品を表し、残りの空間が物品iをリュックサックに入れることを許可すれば、左のサブツリーを広げる.リュックサックを入れてはならず,限界条件を判断し,後続が拡張し続けることで最適価値が得られる可能性がある場合は,右子木を拡張する(すなわち,このi物品は入れないが,後続の物品を考慮する).階数が物品の個数に達すると,拡張を続けるのをやめ,遡及を開始する.
注:どのように遡りますか.どうやって手に入れたのか、どうやって回復したのか.リュックサックに入れた重さを取り出し、bagVに加えた価値をマイナスします.
拘束条件:リュックサックに入れる物品の総質量がリュックサックの容量以下である
限界条件:現在リュックに入れているアイテムの総価値(iおよびそれ以前)＋i以降のアイテムの総価値＜既知の最適値の場合は検索する必要はありません
データ構造:現在リュックサックに入れられている総価値bagV(拡張された)を1つの変数で記録し、後続品の総価値remainV(拡張されていない)を1つの変数で記録し、現在得られている最適値bestV(グローバル状況)、0/1で表される配列bestArr[]でリュックサックに入れたものを記録する.
コア構造:再帰的な考え方で解決する.階層再帰、再帰は果てまで、最適値を保留し、再帰を回復する中で、階層再帰は、元に加えられた重量と価値を回復する.
 

# -*- coding:utf-8 -*-

def Backtrack(t):
    global bestV, bagW, bagV,arr, bestArr, cntV

    if t > n: #          
        if bestV < bagV:
            for i in range(1, n+1):
                bestArr[i] = arr[i]
            bestV = bagV
    else:   #         
        if bagW + listWV[t][0] <= w:    # t           ，     
            arr[t] = True
            bagW += listWV[t][0]
            bagV += listWV[t][1]
            Backtrack(t+1)
            bagW -= listWV[t][0]
            bagV -= listWV[t][1]
        if cntV[t] + bagV > bestV:    #        
            arr[t] = False
            Backtrack(t+1)

if __name__ == '__main__':

    w = int(input())    #    
    n = int(input())    #    

    listWV = [[0,0]]
    listTemp = []
    sumW = 0
    sumV = 0

    for i in range(n):
        listTemp = list(map(int, input().split()))  #    list         list   listWV 
        sumW += listTemp[0]
        sumV += listTemp[1]
        listWV.append(listTemp) #              

    bestV = 0
    bagW = 0
    bagV = 0
    remainV = sumV
    arr = [False for i in range(n+1)]
    bestArr = [False for i in range(n+1)]

    cntV = [0 for i in range(n+1)]  #          ,cnt[i]  i+1~n    
    cntV[0] = sumV
    for i in range(1, n+1):
        cntV[i] = cntV[i-1] - listWV[i][1]

    if sumW <= w:
        print(sumV)
    else:
        Backtrack(1)
        print(bestV)
        print(bestArr)
        print(cntV)

 
検出:

10
5
2 6
5 3
4 5
2 4
3 6

17
[False, True, False, True, False, True]
[24, 18, 15, 10, 6, 0]