{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "96a73f12",
   "metadata": {},
   "source": [
    "---\n",
    "title: \"The knapsack problem\"\n",
    "type: docs\n",
    "date: 2023-06-23\n",
    "math: \"true\"\n",
    "weight: 103\n",
    "description: >\n",
    "  A model for the knapsack problem.\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "45355298",
   "metadata": {},
   "source": [
    "_This file can be downloaded as a [jupyter notebook](https://jupyter.org/) and executed with a [Java kernel](https://github.com/SpencerPark/IJava). The next cell is then used to add the dependency to choco and can be ignored otherwise._ \n",
    "\n",
    "[>> ipynb <<](</notebooks/content/en/tutos/Other examples/The_knapsack_problem.ipynb>)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "2a90fd6a",
   "metadata": {},
   "outputs": [],
   "source": [
    "// Add maven dependencies at runtime \n",
    "%maven org.choco-solver:choco-solver:4.10.13"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6acd1cce",
   "metadata": {},
   "source": [
    "------ \n",
    "<a href=\"http://en.wikipedia.org/wiki/Knapsack_problem\">Wikipedia</a>:<br/>\n",
    "> Given a set of items, each with a weight and a value, determine the count of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible. It derives its name from the problem faced by someone who is constrained by a fixed-size knapsack and must fill it with the most useful items.\""
   ]
  },
  {
   "cell_type": "markdown",
   "id": "aad1b076",
   "metadata": {},
   "source": [
    "First manage imports."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "4381af83",
   "metadata": {},
   "outputs": [],
   "source": [
    "import org.chocosolver.solver.Model;\n",
    "import org.chocosolver.solver.Solver;\n",
    "import org.chocosolver.solver.exception.ContradictionException;\n",
    "import org.chocosolver.solver.variables.IntVar;\n",
    "\n",
    "import java.util.Arrays;\n",
    "\n",
    "import static org.chocosolver.solver.search.strategy.Search.inputOrderLBSearch;\n",
    "import static org.chocosolver.solver.search.strategy.Search.inputOrderUBSearch;"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f7715dc8",
   "metadata": {},
   "source": [
    "## Input data\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "e84eb32a",
   "metadata": {},
   "outputs": [],
   "source": [
    "int n = 10; // number of different items\n",
    "int W = 67; // a maximum weight capacity \n",
    "int[] w = new int[]{23, 26,20,18,32, 27, 29, 26, 30, 27}; // weight of items\n",
    "int[] v = new int[]{505, 352, 458, 220, 354, 414, 498, 545, 473, 543}; // value of items"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "231df9b7",
   "metadata": {},
   "source": [
    "## The model"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e0a5f734",
   "metadata": {},
   "source": [
    "Then, we can start modelling the problem with choco.\n",
    "The first step is to defined a `Model` instance.\n",
    "It is required to declare and store the variables and the constraints.\n",
    "For convenience, an instance can be declared with a name."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "a78f8a49",
   "metadata": {},
   "outputs": [],
   "source": [
    "Model model = new Model(\"Knapsack\");"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6c85faba",
   "metadata": {},
   "source": [
    "For each object, a variable is declared to count the number of times it appears in the knapsack."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "02a3b9c2",
   "metadata": {},
   "outputs": [],
   "source": [
    "IntVar[] items = new IntVar[n];\n",
    "for (int i = 0; i < n; i++) {\n",
    "    items[i] = model.intVar(\"item_\" + (i + 1), 0, (int) Math.ceil(W*1. / w[i]));\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "964bd213",
   "metadata": {},
   "source": [
    "The paramaters are:\n",
    "- the prefix for setting the variables' name,\n",
    "- the lower bound and the upper bound of each variable.\n",
    "\n",
    "**Remark:**\n",
    "*To model 0-1 knapsack problem, the upper bound of each variable must be set to $1$.*\n",
    "\n",
    "The problem is to maximize the sum of the values of the items in the knapsack.\n",
    "This amount is maintained in a variable:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "9232a895",
   "metadata": {},
   "outputs": [],
   "source": [
    "IntVar value = model.intVar(\"value\", 0, Arrays.stream(v).max().orElse(999) * n);"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "50b4b5ae",
   "metadata": {},
   "source": [
    "The sum of the weights is less than or equal to the knapsack's capacity:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "581d3ffe",
   "metadata": {},
   "outputs": [],
   "source": [
    "IntVar weight = model.intVar(\"weight\", 0, W);"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d93b09e8",
   "metadata": {},
   "source": [
    "All variables are now declared, the `knapsack` constraint can be declared:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "a5417e4b",
   "metadata": {},
   "outputs": [],
   "source": [
    "model.knapsack(items, weight, value, w, v).post();"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ae59c44b",
   "metadata": {},
   "source": [
    "The `value` variable has to be maximized:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "d09123e1",
   "metadata": {},
   "outputs": [],
   "source": [
    "model.setObjective(Model.MAXIMIZE, value);"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c90deecb",
   "metadata": {},
   "source": [
    "## Finding the optimal solution"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a1e74a10",
   "metadata": {},
   "source": [
    "Now that the model is ready, the solving step can be set up.\n",
    "Here we define a top-down maximization:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "cfcc4900",
   "metadata": {},
   "outputs": [],
   "source": [
    "Solver solver = model.getSolver();\n",
    "solver.setSearch(\n",
    "    inputOrderUBSearch(value), \n",
    "    inputOrderLBSearch(items));"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "69977a2f",
   "metadata": {},
   "source": [
    "Let's execute the solving:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "d1fc77de",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Knapsack -- 10 items\n",
      "\tItem: Count\n",
      "\tItem #1: 2\n",
      "\tItem #2: 0\n",
      "\tItem #3: 1\n",
      "\tItem #4: 0\n",
      "\tItem #5: 0\n",
      "\tItem #6: 0\n",
      "\tItem #7: 0\n",
      "\tItem #8: 0\n",
      "\tItem #9: 0\n",
      "\tItem #10: 0\n",
      "\n",
      "\tWeight: 66\n",
      "\n",
      "\tValue: 1468\n"
     ]
    }
   ],
   "source": [
    "while (solver.solve()) {\n",
    "    System.out.printf(\"Knapsack -- %d items\\n\", n);\n",
    "    System.out.println(\"\\tItem: Count\");\n",
    "    for (int i = 0; i < items.length; i++) {\n",
    "        System.out.printf(\"\\tItem #%d: %d\\n\", (i+1), items[i].getValue());\n",
    "    }\n",
    "    System.out.printf(\"\\n\\tWeight: %d\\n\", weight.getValue());\n",
    "    System.out.printf(\"\\n\\tValue: %d\\n\", value.getValue());\n",
    "}\n",
    "solver.reset(); // to solve the model several times"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "095b4d94",
   "metadata": {},
   "source": [
    "The optimal value for this instance of the knapsack problem is $1468$ with a total weight of $66$.\n",
    "\n",
    "When turned to a 0-1 knapsack problem, the optimal value is $1270$ with a total weight of $67$."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Java",
   "language": "java",
   "name": "java"
  },
  "language_info": {
   "codemirror_mode": "java",
   "file_extension": ".jshell",
   "mimetype": "text/x-java-source",
   "name": "Java",
   "pygments_lexer": "java",
   "version": "11.0.1+13-LTS"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}