Fractional Knapsack

fractional_knapsack.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "source": [
    "# Fractional Knapsack Problem\n",
    "\n",
    "## Problem Introduction\n",
    "A thief finds much more loot than his bag can fit. Help him to find the most valuable combination\n",
    "of items assuming that any fraction of a loot item can be put into his bag. [1]\n",
    "\n",
    "## Problem Description\n",
    "### Task\n",
    "The goal of this code problem is to implement an algorithm for the fractional knapsack problem.\n",
    "\n",
    "### Input Format\n",
    "The first line of the input contains the number $n$ of items and the capacity $W$ of a knapsack.\n",
    "The next $n$ lines define the values and weights of the items. The $i$-th line contains integers $v_i$ and $w_i$—the\n",
    "value and the weight of $i$-th item, respectively.\n",
    "### Constraints\n",
    "\n",
    "$1 \\leq n \\leq 103$, $0 \\leq W \\leq 2 \\cdot 106$; $0 \\leq v_i \\leq 2 \\cdot 106$, $0 < w_i ≤ 2 \\cdot 106 \\text{ } \\forall \\text{ } 1 \\leq i \\leq n$. All the numbers are integers.\n",
    "\n",
    "### Output Format\n",
    "Output the maximal value of fractions of items that fit into the knapsack. The absolute\n",
    "value of the difference between the answer of your program and the optimal value should be at most\n",
    "$10^{-3}$. To ensure this, output your answer with at least four digits after the decimal point (otherwise\n",
    "your answer, while being computed correctly, can turn out to be wrong because of rounding issues).\n",
    "\n",
    "### Example 1\n",
    "Input:\n",
    "```\n",
    "capacity = 50\n",
    "values = [60, 100, 120]\n",
    "weights = [20, 50, 30]\n",
    "```\n",
    "Output:\n",
    "```\n",
    "180.0000\n",
    "```\n",
    "To achieve the value 180, we take the first item and the third item into the bag.\n",
    "\n",
    "### Example 2\n",
    "Input:\n",
    "```\n",
    "capacity = 10\n",
    "values = [500]\n",
    "weights = [30]\n",
    "```\n",
    "Output:\n",
    "```\n",
    "166.6667\n",
    "```\n",
    "Here, we just take one third of the only available item.\n"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%% md\n"
    }
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "## Solution\n",
    "\n",
    "Dynamic programming is all about using *greedy* approaches to solve problems efficiently. By greedy, we simply mean that by taking the optimal solution to a sequence of smaller *subproblems*, we can combine those subproblem solutions to find the global solution. Keeping this greedy idea in mind is important for intuitively understanding the intuition for this problem. Unlike with the 0-1 knapsack problem, in the fractional knapsack problem we're allowed to use fractional portions of any of the items. So for example let's say we have a knapsack that can hold 7lbs, and there is only one item to consider, a box of candy bars that we value at &#36;10 and that weighs 10lbs; since $10 > 7$ lbs, we can't fit the whole box in our bag. Let's say there are 10 candy bars in the box though; since the whole box weighs 10lbs, that means each bar weighs 1lb. This means we could take out 7 of the bars and put those into our bag.\n",
    "\n",
    "Easy enough. What about the case when we have multiple items though? This is where the greedy idea becomes important. One idea would be to simply fill our bag with the item with the highest $\\frac{\\text{value}}{\\text{weight}}$ ratio. So let's look at the first example:\n",
    "```\n",
    "C = 50                   # Capacity\n",
    "V = [60, 100, 120]       # Item values\n",
    "W = [20, 50, 30]         # Item weights\n",
    "```\n",
    "Following the greedy intuition, we could start be calculating the value-to-weight ratio $R=[\\frac{v_1}{w_1}, \\frac{v_2}{w_2}, ..., \\frac{v_n}{w_n}] = [60/20, 100/50, 120/30] = [3, 2, 4]$. This means on a per unit weight basis, the third item is the most valuable, then the first item, and finally the second item. If we fill our bag in this order, then we can guarantee that we'll have filled the bag optimally. So after calculating the value-to-weight ratio, we should sort the items based on that ratio. This sorting will take $\\mathcal{O}(n \\log n)$ time. (Technically, we could use something like *median-of-medians* algorithm to get the $k$-th largest element in $\\mathcal{O}(n)$ time, but implementing that sorting algorithm would almost certainly be beyond the scope of any interviewer's expectation.)"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%% md\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "***** TEST 01 *****\n",
      "Total Value = 180.0, Total Weight = 50\n",
      "\n",
      "***** TEST 02 *****\n",
      "Total Value = 166.66666666666669, Total Weight = 10\n"
     ]
    }
   ],
   "source": [
    "from typing import Tuple, List, Union\n",
    "\n",
    "\n",
    "def sort_items(W: list, V: list) -> List[int]:\n",
    "    \"\"\" Returns a sorted index of the V, W arrays based on value-to-weight-ratio. \"\"\"\n",
    "    order = [i for i in range(len(W))]\n",
    "    v2r = [v / w for v, w in zip(V, W)]\n",
    "\n",
    "    # Python's built-in 'sorted' method sorts in ascending order. We could reverse that here, but\n",
    "    # instead in our main program we'll simply 'pop' the last element. This eliminates the need\n",
    "    # for doing the reversal, which saves us at least one O(n) operation.\n",
    "    order = [k for k, _ in list(sorted([(i, v) for i, v in zip(order, v2r)], key=lambda x: x[1]))]\n",
    "    return order\n",
    "\n",
    "\n",
    "def knapsack(C: int, W: List[Union[int, float]], V: List[Union[int, float]]) -> Tuple[float, int]:\n",
    "    \"\"\" Solve the fractional knapsack problem. \"\"\"\n",
    "    order = sort_items(W, V)\n",
    "    total_weight = 0\n",
    "    total_value = 0\n",
    "    while order:\n",
    "        i = order.pop()\n",
    "        # If we can fit the entire item in the bag, then do that\n",
    "        if total_weight + W[i] <= C:\n",
    "            total_weight += W[i]\n",
    "            total_value += V[i]\n",
    "        # Otherwise, figure out a fractional amount we can fit in\n",
    "        else:\n",
    "            remaining_cap = C - total_weight\n",
    "            total_value += (V[i] / W[i]) * remaining_cap\n",
    "            total_weight += remaining_cap\n",
    "    return total_value, total_weight\n",
    "\n",
    "\n",
    "\n",
    "def test():\n",
    "    print('\\n***** TEST 01 *****')\n",
    "    val, weight = knapsack(C=50, V=[60, 100, 120], W=[20, 50, 30])\n",
    "    print(f'Total Value = {val}, Total Weight = {weight}')\n",
    "\n",
    "    print('\\n***** TEST 02 *****')\n",
    "    val, weight = knapsack(C=10, V=[500], W=[30])\n",
    "    print(f'Total Value = {val}, Total Weight = {weight}')\n",
    "\n",
    "\n",
    "test()"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "## References\n",
    "\n",
    "[1] [\"Algorithmic Toolbox\". University of California San Diego. Coursera.](https://www.coursera.org/learn/algorithmic-toolbox/programming/kAiGl/programming-assignment-3-greedy-algorithms)"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%% md\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "outputs": [],
   "source": [],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}