{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "This notebook was prepared by [Donne Martin](https://github.com/donnemartin). Source and license info is on [GitHub](https://github.com/donnemartin/interactive-coding-challenges)." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Solution Notebook" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Problem: Given a knapsack with a total weight capacity and a list of items with weight w(i) and value v(i), determine which items to select to maximize total value.\n", "\n", "* [Constraints](#Constraints)\n", "* [Test Cases](#Test-Cases)\n", "* [Algorithm](#Algorithm)\n", "* [Code](#Code)\n", "* [Unit Test](#Unit-Test)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Constraints\n", "\n", "* Can we replace the items once they are placed in the knapsack?\n", " * No, this is the 0/1 knapsack problem\n", "* Can we split an item?\n", " * No\n", "* Can we get an input item with weight of 0 or value of 0?\n", " * No\n", "* Can we assume the inputs are valid?\n", " * No\n", "* Are the inputs in sorted order by val/weight?\n", " * Yes, if not we'd need to sort them first\n", "* Can we assume this fits memory?\n", " * Yes" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Test Cases\n", "\n", "* items or total weight is None -> Exception\n", "* items or total weight is 0 -> 0\n", "* General case\n", "\n", "
```\n",
"total_weight = 8\n",
"items\n",
"  v | w\n",
"  0 | 0\n",
"a 2 | 2\n",
"b 4 | 2\n",
"c 6 | 4\n",
"d 9 | 5\n",
"\n",
"max value = 13\n",
"items\n",
"  v | w\n",
"b 4 | 2\n",
"d 9 | 5 \n",
"```
" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Algorithm\n", "\n", "We'll use bottom up dynamic programming to build a table.\n", "\n", "The solution for the top down approach is also provided below.\n", "\n", "
```\n",
"v = value\n",
"w = weight\n",
"\n",
"               j              \n",
"    -------------------------------------------------\n",
"    | v | w || 0 | 1 | 2 | 3 | 4 | 5 | 6  | 7  | 8  |\n",
"    -------------------------------------------------\n",
"    | 0 | 0 || 0 | 0 | 0 | 0 | 0 | 0 | 0  | 0  | 0  |\n",
"i a | 2 | 2 || 0 | 0 | 2 | 2 | 2 | 2 | 2  | 2  | 2  |\n",
"  b | 4 | 2 || 0 | 0 | 4 | 4 | 6 | 6 | 6  | 6  | 6  |\n",
"  c | 6 | 4 || 0 | 0 | 4 | 4 | 6 | 6 | 10 | 10 | 12 |\n",
"  d | 9 | 5 || 0 | 0 | 4 | 4 | 6 | 9 | 10 | 13 | 13 |\n",
"    -------------------------------------------------\n",
"\n",
"i = row\n",
"j = col\n",
"\n",
"if j >= item[i].weight:\n",
"    T[i][j] = max(item[i].value + T[i - 1][j - item[i].weight],\n",
"                  T[i - 1][j])\n",
"else:\n",
"    T[i][j] = T[i - 1][j]\n",
"```