ナップサック問題を解くPythonプログラムの実装例

はじめに

こんにちは！今回はナップサック問題(Knapsack Problem)をPythonで解くプログラムを紹介します。このプログラムは、動的計画法(Dynamic Programming)を用いて「制限された重量の中で、価値の最大化」を達成するアイテムの組み合わせを求めます。さらに、結果を見やすく表示するためにpandasを活用しています。

ナップサックとは？

• ナップサック問題は次のような最適化問題
• 複数のアイテムであり、それぞれに「重さ」と「価値」が割り当て
• ナップサックの容量が決まっており、その容量を超えないようにアイテムを選択
• 選択したアイテムの総価値を最大化することが目的

実装コード

以下がプログラムの全体コードです。

from decimal import Decimal
import pandas as pd


def knapsack(goods, weights):
    """
    ナップサック問題を動的計画法で解く関数

    Args:
        goods: 各アイテムの名前、重さ、価値を含む辞書
        weights: ナップサックの容量リスト

    Returns:
        動的計画法のテーブルを返す
    """
    n = len(goods)
    table = [[(Decimal(0), [])] * (len(weights)+1) for _ in range(n+1)]
    for i, item in enumerate(goods, 1):
        for j in range(1, len(weights)+1):
            w = goods[item][0]
            w_id = weights.index(w) + 1

            if weights[j-1] < w:
                table[i][j] = table[i-1][j]
            else:
                tmp1 = table[i-1][j][0]
                tmp2 = table[i-1][j-w_id][0] + goods[item][1]
                if tmp1 >= tmp2:
                    table[i][j] = table[i-1][j]
                else:
                    table[i][j] = (tmp2, table[i-1][j-w_id][1] + [item])
    return table


def format_list(data, index_=None, columns_=None):
    """
    動的計画法のテーブルを整形して DataFrame に変換する関数

    Args:
        data: 動的計画法のテーブル
        index_: 行ラベル
        columns_: 列ラベル

    Returns:
        整形された DataFrame
    """
    data = [[(int(value), _) for value, _ in inside] for inside in data]  # Decimalをintに変換

    formatted_list = []
    for sublist in data[1:]:
        tmp = []
        for value, names in sublist[1:]:
            tmp.append(f"({value}, {{{', '.join(names if names else '𝜙')}}})")
        formatted_list.append(tmp)
    return pd.DataFrame(formatted_list, index=index_, columns=columns_)


# 実行例
GOODS = {  # アイテム名: (重さ, 価値)
    'A': (2.5, 200),
    'B': (1, 100),
    'C': (2, 50),
    'D': (0.5, 150),
    'E': (1.5, 200),
}
weights = [Decimal(str(0.5 * i)) for i in range(1, 7)]  # 重さのリスト: [0.5, 1.0, ..., 3.0]

result = knapsack(GOODS, weights)
display(format_list(result, GOODS.keys(), weights))

プログラムの説明

動的計画法を使った解法

動的計画法の考え方を利用して、ナップサック問題を解きます。「価値が最大となる組み合わせ」を表形式で記録しながら計算します。

• knapasck関数は、各重さごとの最大価値を計算し、同時にそのときのアイテムの組み合わせも保存
• format_list関数は計算結果を整形し、DateFrameとして表示

入力データ

• GOODS:各アイテムの重さと価値を表す辞書
• weights:ナップサックに入れられる重さのリスト

実行結果

以下のこのプログラムの実行結果です。

       0.5        1.0       1.5       2.0       2.5       3.0
A  (0, {𝜙})  (0, {𝜙})  (0, {𝜙})  (0, {𝜙})  (200, {A}) (200, {A})
B  (0, {𝜙}) (100, {B}) (100, {B}) (100, {B}) (200, {A}) (200, {A})
C  (0, {𝜙}) (100, {B}) (100, {B}) (100, {B}) (200, {A}) (200, {A})
D  (150, {D}) (150, {D}) (250, {D, B}) (250, {D, B}) (350, {D, A}) (350, {D, A})
E  (150, {D}) (150, {D}) (200, {E}) (350, {D, E}) (350, {D, A}) (450, {D, A, E})

まとめ

ナップサック問題をPythonで解く方法を紹介しました。動的計画法を利用すれば、複雑な最適化問題も効率的に解けます。最後まで読んでくださり、ありがとうございました。もし改善点や質問があれば、ぜひコメントしてください！