【Python】ナップサック問題をKnapsackライブラリで解いてみる

はじめに

こんにちは、がんがんです。
研究室のメンバーが課題で最適化問題を解いており、
自分も気になったので実際に試してみました。

今回は試してみたいだけなので、ライブラリを用いて実験してみます。

目的

1. Knapsackライブラリを用いてナップサック問題を解いてみる

参考

ortoolpyの本家
pypi.org

ライブラリを使用した記事
dev2prod.site

ライブラリを用いて解いてみる

ライブラリとしては、様々なものがあるようです。
それぞれのライブラリの比較は参考記事[2]でやられています。

今回はKnapsackのライブラリを使用してみます。

pip install ortoolpy

コードは以下の通りです。問題としてはよくある重さと価値の最大化問題です。

knapsack.py

# ------------------------------------------------------------
#   Knapsackライブラリによるナップサック問題
# ------------------------------------------------------------
import pysnooper
from ortoolpy import knapsack


@pysnooper.snoop()
def Knapsack(w, v, W):
    res = knapsack(w, v, W)
    print("最大価値：{} / 組み合わせ：{}".format(res[0], res[1]))


if __name__ == '__main__':
    #  重さ(単位：kg)
    w = [4, 2, 2, 1, 10]
    #  価値(単位：$)
    v = [12, 2, 1, 1, 4]
    #  制約：15kg
    W = 15

    Knapsack(w, v, W)

まとめ

今回はライブラリを用いてナップザック問題を解いてみました。
内部構造を考えずに使えるのはさすがです。

具体的に実装する必要はなかったですが(課題が違うから)機会があれば実装してみます。