ナップサック問題は古典的な問題で、複数の変種があります。この節で解決するのは 0-1 ナップサック問題です。

問題は以下の通りです。与えられたナップサックの容量は v で、現在 n 個の品物があり、それらの体積はそれぞれ e1、e2、…、en です。任意の数の品物をナップサックに入れることができますが、それらの体積の和はナップサックの容量 v を超えてはならず、できるだけ v に近いことが望まれます。例えば、ナップサックの容量が 100 の場合、品物体積の和が 99 の方案は 98 の方案よりも良いです。もちろん、体積の和がナップサックの容量 v に等しいのが最善です。私たちが求めるのはこの最適な品物の組み合わせです。

この種の問題の解決策を説明するために、特殊なシナリオを設定しました。このシナリオでは、ナップサックの容量は 10 で、品物は 4 個あり、それらの容量はそれぞれ 1、3、6、8 です。今、私たちはこの最適な品物の組み合わせを計算する必要があります。

最も簡単な方法は、すべての順列と組み合わせを列挙し、それらが条件を満たすかどうかを確認することです。4 個の物体があり、各物体にはナップサックに入れるか入れないかの 2 つの選択肢があります。以下が実装コードです：

goods_list = [1, 3, 6, 8]
def resolve_bag(bag_volume, goods_list):
    biggest_valid_vol = 0
    biggest_valid_selection = []
    goods_num = len(goods_list)
    candidate_num = 1 << goods_num
    for candidate in range(candidate_num):
        selection_decision = []
        for x in range(goods_num):
            if (candidate & 1) == 1:
                selection_decision.append(True)
            else:
                selection_decision.append(False)
            candidate = candidate >> 1
        current_vol = 0
        for x in range(goods_num):
            if selection_decision[x] == True:
                current_vol = current_vol + goods_list[x]
        if current_vol  biggest_valid_vol:
            biggest_valid_vol = current_vol
            biggest_valid_selection = selection_decision
    result = [goods_list[x] for x in range(goods_num) if biggest_valid_selection[x] == True]
    print(result)
resolve_bag(10, goods_list)

実行結果：
[1, 3, 6]

しかし、このプログラムの実行効率は比較的低く、すべての組み合わせを列挙しています。この過程は決定木で表すことができます。

各状態は 2 つの情報で記述できます。1 つはナップサックの残りのスペース、もう 1 つはナップサックに入れていない品物です。例えば、初期状態は残りのスペースが 10 で、ナップサックに入れていない品物の体積は順に 1、3、6、8 です。そして、すべての品物について、右から左に順番にナップサックに入れるかどうかを決定します。例えば、体積が 8 の品物をナップサックに入れると、ナップサックの残りのスペースが 2 で、ナップサックに入れていない品物の容量が 1、3、6 の状態が得られます。体積が 8 の品物をナップサックに入れないと決めると、残りのスペースが 10 で、ナップサックに入れていない品物の体積が 1、3、6 の状態が得られます。

明らかに起こりにくい状態を除くと、図 1 のような状態図が得られます。

図 1：ナップサック問題の状態図

最後に右下の状態、つまり残りのスペースが 0 で、ナップサックが完全に満たされた状態を見つけます。これが私たちの最終状態です。