Skip to content

Instantly share code, notes, and snippets.

@itsvinayak

itsvinayak/knapsack.ipynb

Last active November 2, 2021 08:08
Show Gist options
  • Save itsvinayak/a0cdb23696088cc8ad3cb1efc9b3f29c to your computer and use it in GitHub Desktop.
Save itsvinayak/a0cdb23696088cc8ad3cb1efc9b3f29c to your computer and use it in GitHub Desktop.
Download ZIP
Display the source blob
Display the rendered blob
Raw
knapsack.ipynb
{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# knapsack problem"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The knapsack problem is a problem in combinatorial optimization: \n",
"\n",
"Given a set of items, each with a weight and a value, determine the number 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 valuable items. The problem often arises in resource allocation where the decision makers have to choose from a set of non-divisible projects or tasks under a fixed budget or time constraint, respectively."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## types of knapsack problem\n",
"\n",
"- 0-1 Knapsack Problem\n",
" - for recursive solution time Complexity - <b>O(2^n)</b>\n",
" - using dp time complexity is <b>O(nW)</b> where \"W\" is capacity and \"n\" in no. of item -using DP\n",
"- Unbounded Knapsack (Repetition of items allowed) <b> Θ((W+1)*N) </b>\n",
"- fractional knapsack promble <b>O(nlogn)</b>\n",
"\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## given knapsack \n",
"| 0 | 1 | 2 | 3 | 4 |\n",
"|:-----------:|:-----------:|:-----------:|:-----------:|:-----------:| \n",
"| wt | 10 | 40 | 20 | 30 |\n",
"| val | 60 | 40 | 100| 120|\n",
"| capacity | | 50 |"
]
},
{
"cell_type": "code",
"execution_count": 230,
"metadata": {},
"outputs": [],
"source": [
"wt = [10,40,20,30]\n",
"val = [60,40,100,120]\n",
"capacity = 50"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 0-1 knapsack problem (Unbounded Knapsack (Repetition of items not allowed)"
]
},
{
"cell_type": "code",
"execution_count": 203,
"metadata": {},
"outputs": [],
"source": [
"### 0-1 Knapsack Problem\n",
"## recursive solution time Complexity - O(2^n)\n",
"\n",
"def zeroOneKnapsackRec(index,wt,val,capacity):\n",
" # base condition\n",
" if capacity == 0 or index == 0:\n",
" return 0\n",
" elif wt[index-1] > capacity:\n",
" return zeroOneKnapsackRec(index-1,wt,val,capacity)\n",
" else:\n",
" # if we take or leave\n",
" return max(val[index-1]\n",
" + zeroOneKnapsackRec(index-1,wt,val,capacity-wt[index-1]), # taking element\n",
" zeroOneKnapsackRec(index-1,wt,val,capacity) # leaving element\n",
" )"
]
},
{
"cell_type": "code",
"execution_count": 204,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"220"
]
},
"execution_count": 204,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"zeroOneKnapsackRec(len(wt),wt,val,capacity)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### now using dp on recursive solution \n",
"\n",
"## Type of dynamic programming approach\n",
"\n",
"- top-down approach( Memoization Technique (an extension of recursive approach) )\n",
"- bottom-up approach\n",
" "
]
},
{
"cell_type": "code",
"execution_count": 205,
"metadata": {},
"outputs": [],
"source": [
"# Memoization Technique ... \n",
"\n",
"# Time Complexity: O(number of items*capacity).\n",
"\n",
"# we have taken capacity and weigth because both variables are changing\n",
"dp = [[None for i in range(capacity + 1)] for j in range(len(wt) + 1)] ## array to store recursive call or for Memoization\n",
"\n",
"def zeroOneKnapsackMemoization(index,wt,val,capacity):\n",
" # base condition\n",
" if capacity == 0 or index == 0:\n",
" return 0\n",
" \n",
" if dp[index][capacity] is not None:\n",
" return dp[index][capacity]\n",
" else: \n",
" if wt[index-1] > capacity:\n",
" dp[index][capacity] = zeroOneKnapsackRec(index-1,wt,val,capacity)\n",
" return dp[index][capacity]\n",
" else:\n",
" dp[index][capacity] = max(val[index-1] \\\n",
" + zeroOneKnapsackRec(index-1,wt,val,capacity-wt[index-1]) ,\\\n",
" zeroOneKnapsackRec(index-1,wt,val,capacity-wt[index-1]))\n",
" \n",
" return dp[index][capacity]\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": 206,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"220"
]
},
"execution_count": 206,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"zeroOneKnapsackMemoization(len(wt),wt,val,capacity)"
]
},
{
"cell_type": "code",
"execution_count": 207,
"metadata": {},
"outputs": [],
"source": [
"def topDownKnapsack(wt,val,capacity):\n",
" dp = [[0 for i in range(capacity+1)] for j in range(len(wt)+1)]\n",
" for i in range(len(wt)+1):\n",
" for j in range(capacity+1):\n",
" if i == 0 or j == 0:\n",
" dp[i][j] = 0\n",
" elif wt[i-1] <= j:\n",
" dp[i][j] = max(\n",
" val[i - 1] + dp[i - 1][j - wt[i - 1]],\n",
" dp[i - 1][j]) \n",
" else:\n",
" dp[i][j] = dp[i - 1][j]\n",
" \n",
" return dp\n"
]
},
{
"cell_type": "code",
"execution_count": 217,
"metadata": {},
"outputs": [
{
"data": {
"text/html": [
"<div>\n",
"<style scoped>\n",
" .dataframe tbody tr th:only-of-type {\n",
" vertical-align: middle;\n",
" }\n",
"\n",
" .dataframe tbody tr th {\n",
" vertical-align: top;\n",
" }\n",
"\n",
" .dataframe thead th {\n",
" text-align: right;\n",
" }\n",
"</style>\n",
"<table border=\"1\" class=\"dataframe\">\n",
" <thead>\n",
" <tr style=\"text-align: right;\">\n",
" <th></th>\n",
" <th>0</th>\n",
" <th>1</th>\n",
" <th>2</th>\n",
" <th>3</th>\n",
" <th>4</th>\n",
" <th>5</th>\n",
" <th>6</th>\n",
" <th>7</th>\n",
" <th>8</th>\n",
" <th>9</th>\n",
" <th>10</th>\n",
" <th>11</th>\n",
" <th>12</th>\n",
" <th>13</th>\n",
" <th>14</th>\n",
" <th>15</th>\n",
" <th>16</th>\n",
" <th>17</th>\n",
" <th>18</th>\n",
" <th>19</th>\n",
" <th>20</th>\n",
" <th>21</th>\n",
" <th>22</th>\n",
" <th>23</th>\n",
" <th>24</th>\n",
" <th>25</th>\n",
" <th>26</th>\n",
" <th>27</th>\n",
" <th>28</th>\n",
" <th>29</th>\n",
" <th>30</th>\n",
" <th>31</th>\n",
" <th>32</th>\n",
" <th>33</th>\n",
" <th>34</th>\n",
" <th>35</th>\n",
" <th>36</th>\n",
" <th>37</th>\n",
" <th>38</th>\n",
" <th>39</th>\n",
" <th>40</th>\n",
" <th>41</th>\n",
" <th>42</th>\n",
" <th>43</th>\n",
" <th>44</th>\n",
" <th>45</th>\n",
" <th>46</th>\n",
" <th>47</th>\n",
" <th>48</th>\n",
" <th>49</th>\n",
" <th>50</th>\n",
" </tr>\n",
" </thead>\n",
" <tbody>\n",
" <tr>\n",
" <th>0</th>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" </tr>\n",
" <tr>\n",
" <th>1</th>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" </tr>\n",
" <tr>\n",
" <th>2</th>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>100</td>\n",
" </tr>\n",
" <tr>\n",
" <th>3</th>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>100</td>\n",
" <td>100</td>\n",
" <td>100</td>\n",
" <td>100</td>\n",
" <td>100</td>\n",
" <td>100</td>\n",
" <td>100</td>\n",
" <td>100</td>\n",
" <td>100</td>\n",
" <td>100</td>\n",
" <td>160</td>\n",
" <td>160</td>\n",
" <td>160</td>\n",
" <td>160</td>\n",
" <td>160</td>\n",
" <td>160</td>\n",
" <td>160</td>\n",
" <td>160</td>\n",
" <td>160</td>\n",
" <td>160</td>\n",
" <td>160</td>\n",
" <td>160</td>\n",
" <td>160</td>\n",
" <td>160</td>\n",
" <td>160</td>\n",
" <td>160</td>\n",
" <td>160</td>\n",
" <td>160</td>\n",
" <td>160</td>\n",
" <td>160</td>\n",
" <td>160</td>\n",
" </tr>\n",
" <tr>\n",
" <th>4</th>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>100</td>\n",
" <td>100</td>\n",
" <td>100</td>\n",
" <td>100</td>\n",
" <td>100</td>\n",
" <td>100</td>\n",
" <td>100</td>\n",
" <td>100</td>\n",
" <td>100</td>\n",
" <td>100</td>\n",
" <td>160</td>\n",
" <td>160</td>\n",
" <td>160</td>\n",
" <td>160</td>\n",
" <td>160</td>\n",
" <td>160</td>\n",
" <td>160</td>\n",
" <td>160</td>\n",
" <td>160</td>\n",
" <td>160</td>\n",
" <td>180</td>\n",
" <td>180</td>\n",
" <td>180</td>\n",
" <td>180</td>\n",
" <td>180</td>\n",
" <td>180</td>\n",
" <td>180</td>\n",
" <td>180</td>\n",
" <td>180</td>\n",
" <td>180</td>\n",
" <td>220</td>\n",
" </tr>\n",
" </tbody>\n",
"</table>\n",
"</div>"
],
"text/plain": [
" 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 \\\n",
"0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \n",
"1 0 0 0 0 0 0 0 0 0 0 60 60 60 60 60 60 60 60 60 \n",
"2 0 0 0 0 0 0 0 0 0 0 60 60 60 60 60 60 60 60 60 \n",
"3 0 0 0 0 0 0 0 0 0 0 60 60 60 60 60 60 60 60 60 \n",
"4 0 0 0 0 0 0 0 0 0 0 60 60 60 60 60 60 60 60 60 \n",
"\n",
" 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 \\\n",
"0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \n",
"1 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 \n",
"2 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 \n",
"3 60 100 100 100 100 100 100 100 100 100 100 160 160 160 160 \n",
"4 60 100 100 100 100 100 100 100 100 100 100 160 160 160 160 \n",
"\n",
" 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 \\\n",
"0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \n",
"1 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 \n",
"2 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 \n",
"3 160 160 160 160 160 160 160 160 160 160 160 160 160 160 160 \n",
"4 160 160 160 160 160 160 180 180 180 180 180 180 180 180 180 \n",
"\n",
" 49 50 \n",
"0 0 0 \n",
"1 60 60 \n",
"2 60 100 \n",
"3 160 160 \n",
"4 180 220 "
]
},
"execution_count": 217,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# to see dp table\n",
"from pandas import *\n",
"matrix = topDownKnapsack(wt,val,capacity)\n",
"df = DataFrame(matrix)\n",
"df\n"
]
},
{
"cell_type": "code",
"execution_count": 199,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"ans : 220\n"
]
}
],
"source": [
"print(\"ans :\",topDownKnapsack(wt,val,capacity)[len(wt)][capacity])"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Unbounded Knapsack (Repetition of items allowed)"
]
},
{
"cell_type": "code",
"execution_count": 250,
"metadata": {},
"outputs": [],
"source": [
"def recursiveUnboundedKnapsack(val, wt, W, n):\n",
" \"\"\"\n",
" W = capacity,\n",
" n = index\n",
" \"\"\"\n",
" if n == 0 or W == 0:\n",
" return 0\n",
" elif wt[n - 1] > W:\n",
" return recursiveUnboundedKnapsack(val, wt, W, n-1)\n",
" else:\n",
" return max(\n",
" val[n - 1] + recursiveUnboundedKnapsack(val, wt, W - wt[n - 1], n),\n",
" recursiveUnboundedKnapsack(val, wt, W, n-1),\n",
" )"
]
},
{
"cell_type": "code",
"execution_count": 251,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"300"
]
},
"execution_count": 251,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"recursiveUnboundedKnapsack(val, wt, capacity, len(wt))"
]
},
{
"cell_type": "code",
"execution_count": 262,
"metadata": {},
"outputs": [],
"source": [
"def unboundedKnapsackDp(val, wt, W, n):\n",
" \"\"\"\n",
" W = capacity,\n",
" n = index\n",
" \"\"\"\n",
" dp = [[0 for _ in range(W + 1)] for _ in range(n + 1)]\n",
"\n",
" for i in range(n + 1):\n",
" for j in range(W + 1):\n",
" if i == 0 or j == 0:\n",
" dp[i][j] = 0\n",
" elif wt[i - 1] > j:\n",
" dp[i][j] = dp[i - 1][j]\n",
" else:\n",
" dp[i][j] = max(val[i - 1] + dp[i][j - wt[i - 1]], dp[i - 1][j])\n",
" return dp"
]
},
{
"cell_type": "code",
"execution_count": 264,
"metadata": {},
"outputs": [
{
"data": {
"text/html": [
"<div>\n",
"<style scoped>\n",
" .dataframe tbody tr th:only-of-type {\n",
" vertical-align: middle;\n",
" }\n",
"\n",
" .dataframe tbody tr th {\n",
" vertical-align: top;\n",
" }\n",
"\n",
" .dataframe thead th {\n",
" text-align: right;\n",
" }\n",
"</style>\n",
"<table border=\"1\" class=\"dataframe\">\n",
" <thead>\n",
" <tr style=\"text-align: right;\">\n",
" <th></th>\n",
" <th>0</th>\n",
" <th>1</th>\n",
" <th>2</th>\n",
" <th>3</th>\n",
" <th>4</th>\n",
" <th>5</th>\n",
" <th>6</th>\n",
" <th>7</th>\n",
" <th>8</th>\n",
" <th>9</th>\n",
" <th>10</th>\n",
" <th>11</th>\n",
" <th>12</th>\n",
" <th>13</th>\n",
" <th>14</th>\n",
" <th>15</th>\n",
" <th>16</th>\n",
" <th>17</th>\n",
" <th>18</th>\n",
" <th>19</th>\n",
" <th>20</th>\n",
" <th>21</th>\n",
" <th>22</th>\n",
" <th>23</th>\n",
" <th>24</th>\n",
" <th>25</th>\n",
" <th>26</th>\n",
" <th>27</th>\n",
" <th>28</th>\n",
" <th>29</th>\n",
" <th>30</th>\n",
" <th>31</th>\n",
" <th>32</th>\n",
" <th>33</th>\n",
" <th>34</th>\n",
" <th>35</th>\n",
" <th>36</th>\n",
" <th>37</th>\n",
" <th>38</th>\n",
" <th>39</th>\n",
" <th>40</th>\n",
" <th>41</th>\n",
" <th>42</th>\n",
" <th>43</th>\n",
" <th>44</th>\n",
" <th>45</th>\n",
" <th>46</th>\n",
" <th>47</th>\n",
" <th>48</th>\n",
" <th>49</th>\n",
" <th>50</th>\n",
" </tr>\n",
" </thead>\n",
" <tbody>\n",
" <tr>\n",
" <th>0</th>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" </tr>\n",
" <tr>\n",
" <th>1</th>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>120</td>\n",
" <td>120</td>\n",
" <td>120</td>\n",
" <td>120</td>\n",
" <td>120</td>\n",
" <td>120</td>\n",
" <td>120</td>\n",
" <td>120</td>\n",
" <td>120</td>\n",
" <td>120</td>\n",
" <td>180</td>\n",
" <td>180</td>\n",
" <td>180</td>\n",
" <td>180</td>\n",
" <td>180</td>\n",
" <td>180</td>\n",
" <td>180</td>\n",
" <td>180</td>\n",
" <td>180</td>\n",
" <td>180</td>\n",
" <td>240</td>\n",
" <td>240</td>\n",
" <td>240</td>\n",
" <td>240</td>\n",
" <td>240</td>\n",
" <td>240</td>\n",
" <td>240</td>\n",
" <td>240</td>\n",
" <td>240</td>\n",
" <td>240</td>\n",
" <td>300</td>\n",
" </tr>\n",
" <tr>\n",
" <th>2</th>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>120</td>\n",
" <td>120</td>\n",
" <td>120</td>\n",
" <td>120</td>\n",
" <td>120</td>\n",
" <td>120</td>\n",
" <td>120</td>\n",
" <td>120</td>\n",
" <td>120</td>\n",
" <td>120</td>\n",
" <td>180</td>\n",
" <td>180</td>\n",
" <td>180</td>\n",
" <td>180</td>\n",
" <td>180</td>\n",
" <td>180</td>\n",
" <td>180</td>\n",
" <td>180</td>\n",
" <td>180</td>\n",
" <td>180</td>\n",
" <td>240</td>\n",
" <td>240</td>\n",
" <td>240</td>\n",
" <td>240</td>\n",
" <td>240</td>\n",
" <td>240</td>\n",
" <td>240</td>\n",
" <td>240</td>\n",
" <td>240</td>\n",
" <td>240</td>\n",
" <td>300</td>\n",
" </tr>\n",
" <tr>\n",
" <th>3</th>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>120</td>\n",
" <td>120</td>\n",
" <td>120</td>\n",
" <td>120</td>\n",
" <td>120</td>\n",
" <td>120</td>\n",
" <td>120</td>\n",
" <td>120</td>\n",
" <td>120</td>\n",
" <td>120</td>\n",
" <td>180</td>\n",
" <td>180</td>\n",
" <td>180</td>\n",
" <td>180</td>\n",
" <td>180</td>\n",
" <td>180</td>\n",
" <td>180</td>\n",
" <td>180</td>\n",
" <td>180</td>\n",
" <td>180</td>\n",
" <td>240</td>\n",
" <td>240</td>\n",
" <td>240</td>\n",
" <td>240</td>\n",
" <td>240</td>\n",
" <td>240</td>\n",
" <td>240</td>\n",
" <td>240</td>\n",
" <td>240</td>\n",
" <td>240</td>\n",
" <td>300</td>\n",
" </tr>\n",
" <tr>\n",
" <th>4</th>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>60</td>\n",
" <td>120</td>\n",
" <td>120</td>\n",
" <td>120</td>\n",
" <td>120</td>\n",
" <td>120</td>\n",
" <td>120</td>\n",
" <td>120</td>\n",
" <td>120</td>\n",
" <td>120</td>\n",
" <td>120</td>\n",
" <td>180</td>\n",
" <td>180</td>\n",
" <td>180</td>\n",
" <td>180</td>\n",
" <td>180</td>\n",
" <td>180</td>\n",
" <td>180</td>\n",
" <td>180</td>\n",
" <td>180</td>\n",
" <td>180</td>\n",
" <td>240</td>\n",
" <td>240</td>\n",
" <td>240</td>\n",
" <td>240</td>\n",
" <td>240</td>\n",
" <td>240</td>\n",
" <td>240</td>\n",
" <td>240</td>\n",
" <td>240</td>\n",
" <td>240</td>\n",
" <td>300</td>\n",
" </tr>\n",
" </tbody>\n",
"</table>\n",
"</div>"
],
"text/plain": [
" 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 \\\n",
"0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \n",
"1 0 0 0 0 0 0 0 0 0 0 60 60 60 60 60 60 60 60 60 \n",
"2 0 0 0 0 0 0 0 0 0 0 60 60 60 60 60 60 60 60 60 \n",
"3 0 0 0 0 0 0 0 0 0 0 60 60 60 60 60 60 60 60 60 \n",
"4 0 0 0 0 0 0 0 0 0 0 60 60 60 60 60 60 60 60 60 \n",
"\n",
" 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 \\\n",
"0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \n",
"1 60 120 120 120 120 120 120 120 120 120 120 180 180 180 180 \n",
"2 60 120 120 120 120 120 120 120 120 120 120 180 180 180 180 \n",
"3 60 120 120 120 120 120 120 120 120 120 120 180 180 180 180 \n",
"4 60 120 120 120 120 120 120 120 120 120 120 180 180 180 180 \n",
"\n",
" 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 \\\n",
"0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \n",
"1 180 180 180 180 180 180 240 240 240 240 240 240 240 240 240 \n",
"2 180 180 180 180 180 180 240 240 240 240 240 240 240 240 240 \n",
"3 180 180 180 180 180 180 240 240 240 240 240 240 240 240 240 \n",
"4 180 180 180 180 180 180 240 240 240 240 240 240 240 240 240 \n",
"\n",
" 49 50 \n",
"0 0 0 \n",
"1 240 300 \n",
"2 240 300 \n",
"3 240 300 \n",
"4 240 300 "
]
},
"execution_count": 264,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# to see dp table\n",
"from pandas import *\n",
"matrix = unboundedKnapsackDp(val, wt, capacity, len(wt))\n",
"df = DataFrame(matrix)\n",
"df"
]
},
{
"cell_type": "code",
"execution_count": 267,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"ans : 300\n"
]
}
],
"source": [
"print(\"ans :\",unboundedKnapsackDp(val, wt, capacity, len(wt))[len(wt)][capacity])"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## fractional knapsack promble (greedy approch)"
]
},
{
"cell_type": "code",
"execution_count": 80,
"metadata": {},
"outputs": [],
"source": [
"class item(object):\n",
" \"\"\" class to store item \"\"\"\n",
" def __init__(self,wt,val,index):\n",
" self.wt = wt\n",
" self.val = val\n",
" self.index = index\n",
" self.cost = val // wt\n",
" def __lt__(self, other):\n",
" return self.cost < other.cost"
]
},
{
"cell_type": "code",
"execution_count": 81,
"metadata": {},
"outputs": [],
"source": [
"class build_item_list:\n",
" \"\"\" class to build item list \"\"\"\n",
" def __init__(self,wt_list,val_list):\n",
" self.wt_list = wt_list\n",
" self.val_list = val_list\n",
" def build(self):\n",
" item_list = []\n",
" for index in range(len(self.wt_list)):\n",
" item_list.append(item(self.wt_list[index],self.val_list[index],index))\n",
" return item_list"
]
},
{
"cell_type": "code",
"execution_count": 82,
"metadata": {},
"outputs": [],
"source": [
"class FractionalKnapSack(object):\n",
" \"\"\" knapsack sol class \"\"\"\n",
" def __init__(self,wt_list,val_list,capacity):\n",
" # Builder design pattern\n",
" self.item_list = build_item_list(wt_list,val_list).build()\n",
" self.capacity = capacity\n",
" self.totalValue = 0\n",
" self.totalValue = self.getMaxValue() \n",
" \n",
" def getMaxValue(self):\n",
" \"\"\" function return max val a knapsack can hold\"\"\"\n",
" self.item_list.sort(reverse=True)\n",
" for i in self.item_list:\n",
" curWt = int(i.wt)\n",
" curVal = int(i.val)\n",
" if self.capacity - curWt >= 0:\n",
" self.capacity -= curWt\n",
" self.totalValue += curVal\n",
" else:\n",
" fraction = self.capacity / curWt\n",
" self.totalValue += curVal * fraction\n",
" self.capacity = int(self.capacity - (curWt * fraction))\n",
" break\n",
" return self.totalValue\n",
" \n",
" def __repr__(self):\n",
" return f\" Total value of knapsack is {self.totalValue}\"\n",
" \n",
" def __str__(self):\n",
" return f\" Total value of knapsack is {self.totalValue}\""
]
},
{
"cell_type": "code",
"execution_count": 83,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
" Total value of knapsack is 240.0"
]
},
"execution_count": 83,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"FractionalKnapSack(wt,val,capacity)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### by vinayak "
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"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.8.5"
}
},
"nbformat": 4,
"nbformat_minor": 4
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment