{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Knapsack Problem\n",
    "\n",
    "Bin packing tried to minimize the number of bins needed for a fixed number of items, if we instead fix the number of bins and assign some way to value objects, then the knapsack problem tells us which objects to take to maximize our total item value. Rather than object sizes, in the traditional formulation we consider item weights and imagine that we are packing a backpack for a camping trip or a suitcase for a vacation. \n",
    "\n",
    "How many items of different weights can we fit in our suitcase before our suitcase is too heavy. Which objects should we take?\n",
    "\n",
    "This problems is also known as the capital budgeting problem. Instead of items we think of investment opportunities, instead of value we consider investment return, weight becomes value, and the maximum weight we can carry becomes our budget. Which investments should we take on to maximize our return with the current budget?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from pulp import *\n",
    "import numpy as np"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1. First lets make some fake data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "items=['item_%d'%i for i in range(20)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "item_weights = dict( (i,np.random.randint(1,20)) for i in items)\n",
    "item_values = dict( (i,10*np.random.rand()) for i in items)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "W = 100"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "#variables. How many of each object to take. For simplicity lets make this 0 or 1 (classic 0-1 knapsack problem)\n",
    "x = LpVariable.dicts('item',items,0,1, LpBinary)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "#create the problme\n",
    "prob=LpProblem(\"knapsack\",LpMaximize)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "#the objective\n",
    "cost = lpSum([ item_values[i]*x[i] for i in items])\n",
    "prob+=cost"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "#constraint\n",
    "prob += lpSum([ item_weights[i]*x[i] for i in items]) <= W"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solve it!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 2.45 ms, sys: 4.37 ms, total: 6.82 ms\n",
      "Wall time: 20.5 ms\n",
      "Optimal\n"
     ]
    }
   ],
   "source": [
    "%time prob.solve()\n",
    "print(LpStatus[prob.status])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And the result:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "item_0 1.0\n",
      "item_1 1.0\n",
      "item_2 1.0\n",
      "item_3 1.0\n",
      "item_4 1.0\n",
      "item_5 0.0\n",
      "item_6 0.0\n",
      "item_7 1.0\n",
      "item_8 1.0\n",
      "item_9 0.0\n",
      "item_10 1.0\n",
      "item_11 0.0\n",
      "item_12 1.0\n",
      "item_13 1.0\n",
      "item_14 0.0\n",
      "item_15 1.0\n",
      "item_16 0.0\n",
      "item_17 0.0\n",
      "item_18 0.0\n",
      "item_19 0.0\n"
     ]
    }
   ],
   "source": [
    "for i in items:\n",
    "    print(i, value(x[i]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "76.56871781489664\n"
     ]
    }
   ],
   "source": [
    "print(value(prob.objective))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "100.0\n"
     ]
    }
   ],
   "source": [
    "print(sum([ item_weights[i]*value(x[i]) for i in items]))"
   ]
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python [conda env:py3]",
   "language": "python",
   "name": "conda-env-py3-py"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}