knapsack.ipynb

knapsack.ipynb

{
  "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
        }
      ]
    }
  ]
}

COIN-OR https://coin-or.github.io/pulp/index.html#
pypi PuLP https://pypi.org/project/PuLP/