Created
February 5, 2021 16:58
-
-
Save geojackass/5b4c25a4db28aaa6a28990c646c8c0a5 to your computer and use it in GitHub Desktop.
knapsack.ipynb
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
{ | |
"nbformat": 4, | |
"nbformat_minor": 0, | |
"metadata": { | |
"colab": { | |
"name": "knapsack.ipynb", | |
"provenance": [], | |
"authorship_tag": "ABX9TyODdfsSF6P+sqE8Aj23ToV0", | |
"include_colab_link": true | |
}, | |
"kernelspec": { | |
"name": "python3", | |
"display_name": "Python 3" | |
} | |
}, | |
"cells": [ | |
{ | |
"cell_type": "markdown", | |
"metadata": { | |
"id": "view-in-github", | |
"colab_type": "text" | |
}, | |
"source": [ | |
"<a href=\"https://colab.research.google.com/gist/geojackass/5b4c25a4db28aaa6a28990c646c8c0a5/knapsack.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>" | |
] | |
}, | |
{ | |
"cell_type": "markdown", | |
"metadata": { | |
"id": "Y5hwlHEIEEI0" | |
}, | |
"source": [ | |
"### ナップサック問題としての予算の制約問題\r\n", | |
"- 与えられた予算の中で,使用可能な最大金額となるように,予算を使用する.使用可能な金額(item) の和が全体の金額(budget) を超えないように,金額の価値=優先度(weight) の和を最大にする.この時優先度が高い方が,weightの値は大きくなるように指定する." | |
] | |
}, | |
{ | |
"cell_type": "code", | |
"metadata": { | |
"colab": { | |
"base_uri": "https://localhost:8080/" | |
}, | |
"id": "l3uu6418DhGO", | |
"outputId": "8ab3c74c-b146-4479-ac53-af7a14b7b29b" | |
}, | |
"source": [ | |
"pip install ortoolpy" | |
], | |
"execution_count": null, | |
"outputs": [ | |
{ | |
"output_type": "stream", | |
"text": [ | |
"Collecting ortoolpy\n", | |
" Downloading https://files.pythonhosted.org/packages/97/8a/7c7ee8c19ca5157c89f498e062ccb421c97cb0ce0c2a77754e09865d9a48/ortoolpy-0.2.30.tar.gz\n", | |
"Requirement already satisfied: pulp in /usr/local/lib/python3.6/dist-packages (from ortoolpy) (2.4)\n", | |
"Requirement already satisfied: amply>=0.1.2 in /usr/local/lib/python3.6/dist-packages (from pulp->ortoolpy) (0.1.4)\n", | |
"Requirement already satisfied: pyparsing in /usr/local/lib/python3.6/dist-packages (from amply>=0.1.2->pulp->ortoolpy) (2.4.7)\n", | |
"Requirement already satisfied: docutils>=0.3 in /usr/local/lib/python3.6/dist-packages (from amply>=0.1.2->pulp->ortoolpy) (0.16)\n", | |
"Building wheels for collected packages: ortoolpy\n", | |
" Building wheel for ortoolpy (setup.py) ... \u001b[?25l\u001b[?25hdone\n", | |
" Created wheel for ortoolpy: filename=ortoolpy-0.2.30-cp36-none-any.whl size=23238 sha256=a9427d134fc81923e7800e872cfc766ecaa4bf11f9bb2bc295be875a08dee4c6\n", | |
" Stored in directory: /root/.cache/pip/wheels/04/b2/96/f6ef2da1545a11cd91ee4bd9da930d588dde5751ac7e088a74\n", | |
"Successfully built ortoolpy\n", | |
"Installing collected packages: ortoolpy\n", | |
"Successfully installed ortoolpy-0.2.30\n" | |
], | |
"name": "stdout" | |
} | |
] | |
}, | |
{ | |
"cell_type": "code", | |
"metadata": { | |
"colab": { | |
"base_uri": "https://localhost:8080/" | |
}, | |
"id": "b52p1IRbAjew", | |
"outputId": "d2cd464a-9760-48d4-a3fd-ee9af23c2b34" | |
}, | |
"source": [ | |
"from ortoolpy import knapsack\r\n", | |
"#item=金額*1000円\r\n", | |
"item = [21, 11, 15, 9, 34, 25, 41, 52]\r\n", | |
"#優先度:itemの合計金額が予算制約を超えないだけでよく,全ての優先度が等しい場合に相当する\r\n", | |
"weight = [1,1,1,1,1,1,1,1]\r\n", | |
"#予算制約\r\n", | |
"budget = 100\r\n", | |
"#item金額の合計が予算制約を超えない,配列のindexはitemのリスト番号が出力される\r\n", | |
"knapsack(item, weight, budget)" | |
], | |
"execution_count": null, | |
"outputs": [ | |
{ | |
"output_type": "execute_result", | |
"data": { | |
"text/plain": [ | |
"(5.0, [0, 1, 2, 3, 5])" | |
] | |
}, | |
"metadata": { | |
"tags": [] | |
}, | |
"execution_count": 11 | |
} | |
] | |
} | |
] | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
COIN-OR https://coin-or.github.io/pulp/index.html#
pypi PuLP https://pypi.org/project/PuLP/