knapsack_example.ipynb

knapsack_example.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "knapsack_example.ipynb",
      "provenance": [],
      "collapsed_sections": [],
      "authorship_tag": "ABX9TyNrvYEhgDqW+q7q0/Yre/Qh",
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/gist/enakai00/5e333e35ddb0e62b40175764d8c8c6a4/knapsack_example.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "IbkYhg6sT3si",
        "outputId": "c6b219d2-0d1a-440b-b94a-2fa52f0365a9"
      },
      "source": [
        "%%writefile input.txt\n",
        "10 2921\n",
        "981421680 325\n",
        "515936168 845\n",
        "17309336 371\n",
        "788067075 112\n",
        "104855562 96\n",
        "494541604 960\n",
        "32007355 161\n",
        "772339969 581\n",
        "55112800 248\n",
        "98577050 22"
      ],
      "execution_count": 1,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Writing input.txt\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "ERuNeVIKT5aK",
        "outputId": "aaacef4f-35b9-4755-9e82-fe654492a61b"
      },
      "source": [
        "import sys\n",
        "\n",
        "def main(f):\n",
        "  v, w = [None], [None]\n",
        "  N, W = list(map(int, f.readline().split()))\n",
        "  for _ in range(N):\n",
        "    v0, w0 = list(map(int, f.readline().split()))\n",
        "    v.append(v0)\n",
        "    w.append(w0)\n",
        "\n",
        "  dp = [ [None] + [0]*W for _ in range(N+1) ]\n",
        "\n",
        "  # n = 1 の場合\n",
        "  for w0 in range(0, W+1):\n",
        "    if w[1] <= w0:\n",
        "      dp[1][w0] = v[1]\n",
        "    else:\n",
        "      dp[1][w0] = 0\n",
        "\n",
        "  # n = 2,...,N の場合\n",
        "  for n in range(2, N+1):\n",
        "    for w0 in range(0, W+1):\n",
        "      case1 = dp[n-1][w0]\n",
        "      if w[n] > w0:\n",
        "        case2 = 0\n",
        "      else:\n",
        "        case2 = dp[n-1][w0-w[n]] + v[n]\n",
        "      dp[n][w0] = max(case1, case2)\n",
        "\n",
        "  print(dp[N][W])\n",
        "\n",
        "#main(sys.stdin)\n",
        "with open('input.txt', 'r') as file:\n",
        "  main(file)"
      ],
      "execution_count": 3,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "3657162058\n"
          ],
          "name": "stdout"
        }
      ]
    }
  ]
}