0-1ナップサック問題入門(if文とfor文と配列を前提とする)

この記事ではナップサック問題を解くプログラムをPythonで実装します。
再帰関数も動的計画法も使わず、if文とfor文と配列を使って解くことを目指します。

ナップサック問題とは

ナップサック問題とは次のような問題です。

いくつかのアイテムと1つのナップサックが与えられる。それぞれのアイテムには重さと価値があり、ナップサックには容量が設定されている。ナップサックの容量の範囲内でアイテム何種類か選び、選んだアイテムの価値の合計を最大化せよ。

各アイテムについてナップサックに入れられる数が0個か1個であることから0-1ナップサック問題と呼ばれることがあります。

具体例

具体例を示します。

ナップサックには 24kgまで入れられます。 アイテムの重さと価値は下記表のとおりです。

名前 重さ(kg) 価値(万円)
A 1 1
B 7 6
C 8 7
D 9 8
E 19 19

{B,C,D}の3つを選ぶと重さ24kg・価値21万円となり、これは価値の最大値になっています。

ナップサック問題の解き方

この問題は、動的計画法という高度なアルゴリズムを使うことで、商品が増えた場合も高速に解を求められることが知られていますが、今回はアイテムがたかだか20個としてしまってif文とfor文を使って素直に実装します。 ループは深いですが、やっている事自体は単純です。

capacity = 24  # ナップサックには 24kgまで入れられる
weights = [1, 7, 8, 9, 19]  # アイテムA-Eの重さ
values = [1, 6, 7, 8, 19]  # アイテムA-Eの価値
total_weight = 0
total_value = 0
max_value = 0

# それぞれ選ばない・選ぶに対応している
for use_A in (False, True):
    if use_A:  # アイテムAを選ぶなら、Aの重さと価値をナップサックに加える
        total_weight += weights[0]
        total_value += values[0]
    for use_B in (False, True):
        if use_B:  # アイテムBを選ぶなら、Bの重さと価値をナップサックに加える
            total_weight += weights[1]
            total_value += values[1]
        for use_C in (False, True):
            if use_C:  # アイテムCを選ぶなら、Cの重さと価値をナップサックに加える
                total_weight += weights[2]
                total_value += values[2]
            for use_D in (False, True):
                if use_D:
                    total_weight += weights[3]
                    total_value += values[3]
                for use_E in (False, True):
                    if use_E:
                        total_weight += weights[4]
                        total_value += values[4]

                    if total_weight <= capacity:
                        # 重さが容量以下かつ、これまでの価値の最大値を現在の価値が上回っている場合は価値の最大値を更新する
                        max_value = max(max_value, total_value)

                    if use_E:  # アイテムEを選んでいたら、Eの重さと価値をナップサックから除く
                        total_weight -= weights[4]
                        total_value -= values[4]
                if use_D:  # アイテムDを選んでいたら、Dの重さと価値をナップサックから除く
                    total_weight -= weights[3]
                    total_value -= values[3]
            if use_C:  # アイテムCを選んでいたら、Cの重さと価値をナップサックから除く
                total_weight -= weights[2]
                total_value -= values[2]
        if use_B:
            total_weight -= weights[1]
            total_value -= values[1]
    if use_A:
        total_weight -= weights[0]
        total_value -= values[0]

print(max_value)

それぞれのアイテムについて、選ばない・選ぶの各2通りのパターンをfor文をネストすることで網羅しています。2*2*2*2*2=32通りのtotal_valueを計算し、価値の最大値を更新しています。

プログラムを動的に生成する

※ここからちょっと難しくなります。

特定の問題(ナップサックの容量やアイテムの重さ・価値が固定)を解くのであれば上記で十分だろうと思いますが、上記のプログラムはアイテムの個数分のfor文のネストを深くする必要があり、アイテム数の変化に対応できません。 上記のアルゴリズムをプログラム自身に実装させてみることにします。つまりアイテムが与えられるとアイテムの個数に応じてループを増やし、全探索を行い、最大値を求める関数を作ります。 ここでのポイントは、プログラムとして成立している文字列を作成するロジックを作りexec関数を使って、文字列をプログラムとみて実行する関数を使うことです。

下記が「ナップサック問題を解くプログラムを作成して実行するプログラム」です。

import textwrap


def search_max_value(capacity: int, weights: list, values: list):
    item_count = len(weights)

    prog = [
        'total_weight = 0',
        'total_value = 0',
        'max_value = 0',
    ]

    item_loop_template = textwrap.dedent("""
        for use_{item_index} in (False, True):
            if use_{item_index}:
                total_weight += weights[{item_index}]
                total_value += values[{item_index}]
    """)
    for i in range(item_count):
        indent = ' '*4*i
        row = textwrap.indent(item_loop_template.format(item_index=i), indent)
        prog.append(row)

    indent = ' '*4*item_count
    prog.append(indent + 'if total_weight <= capacity:')
    prog.append(indent + '    max_value = max(max_value, total_value)')

    item_unloop_template = textwrap.dedent("""
        if use_{item_index}:
            total_weight -= weights[{item_index}]
            total_value -= values[{item_index}]
    """)
    for i in reversed(range(item_count)):
        indent = ' '*4*(i+1)
        row = textwrap.indent(item_unloop_template.format(item_index=i), indent)
        prog.append(row)

    local_vars = {
        'capacity': capacity,
        'weights': weights,
        'values': values,
    }
    exec('\n'.join(prog), None, local_vars)
    # print('\n'.join(prog))  # この行のコメントアウトを外すと実行されているプログラムが標準出力に出力されます
    return local_vars['max_value']

if __name__ == '__main__':
    # 具体的な問題を与える
    capacity = 24
    weights = [1, 7, 8, 9, 19]
    values = [1, 6, 7, 8, 19]
    max_value = search_max_value(capacity, weights, values)
    print(max_value)

textwrapはテキストの折り返しと詰め込みを行う標準ライブラリです。indent関数は3.3で導入されました。

※Pythonの言語仕様上の問題でアイテム数が20を超える問題は上記のプログラムで最大値を求めることができません。より大きなサイズの問題を解きたい場合は再帰関数や動的計画法を勉強しましょう。

ナップサック問題など動的計画法の勉強ように良い書籍があるので、ご興味のある方は見てみてください。

最強最速アルゴリズマー養成講座 プログラミングコンテストTopCoder攻略ガイド

最強最速アルゴリズマー養成講座 プログラミングコンテストTopCoder攻略ガイド

まとめ

この記事ではナップサック問題の典型的な導入である再帰関数・動的計画法という概念を使わず、if文とfor文を使った価値の合計の最大値を求めるプログラムを示しました。 またメタプログラミングを行うことでアイテム数が20以下のケースについて、ナップサック問題の解を求めまるプログラムを実装するプログラムを示しました。

f:id:matsu7874:20190217032530p:plain