All About Knapsack Problem | python
Tags: algorithms, python, programming, showdev
Published: 2021-04-29 07:37:45

The knapsack problem is a problem in combinatorial optimization:

Given a set of items, each with a weight and a value, determine the number of each item included 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.

**Types of knapsack problem:**

- 0-1 Knapsack Problem
     - for recursive solution time Complexity - O(2^n)
     - using dynamic programming time complexity is O(nW) where "W" is capacity and "n" in no. of the item 
- Unbounded Knapsack (Repetition of items allowed) Θ((W+1)*N)
- fractional knapsack problem O(nlogn)

**Given knapsack**
![Screenshot (2).png](https://cdn.hashnode.com/res/hashnode/image/upload/v1619342085603/Z1S1f6z7U.png)


**variables used** 
```
wt = [10,40,20,30]
val = [60,40,100,120]
capacity = 50
``` 

## 0-1 knapsack problem (Unbounded Knapsack (Repetition of items not allowed)



``` 
### 0-1 Knapsack Problem
## recursive solution time Complexity - O(2^n)

def zeroOneKnapsackRec(index,wt,val,capacity):
    # base condition
    if capacity == 0 or index == 0:
        return 0
    elif wt[index-1] > capacity:
        return zeroOneKnapsackRec(index-1,wt,val,capacity)
    else:
        # if we take or leave
        return max(val[index-1]
                   + zeroOneKnapsackRec(index-1,wt,val,capacity-wt[index-1]),  # taking element
                   zeroOneKnapsackRec(index-1,wt,val,capacity)  # leaving element
                    )
zeroOneKnapsackRec(len(wt),wt,val,capacity)
``` 

**Output:** 220
 
### now using dp on a recursive solution 

## Type of dynamic programming approach

- top-down approach( Memoization Technique (an extension of recursive approach) )
- bottom-up approach
 

```
# Memoization Technique ... 

# Time Complexity: O(number of items*capacity).

# we have taken capacity and weigth because both variables are changing
dp = [[None for i in range(capacity + 1)] for j in range(len(wt) + 1)]  ## array to store recursive call or for Memoization

def zeroOneKnapsackMemoization(index,wt,val,capacity):
    # base condition
    if capacity == 0 or index == 0:
        return 0
    
    if dp[index][capacity] is not None:
        return dp[index][capacity]
    else:    
        if wt[index-1] > capacity:
            dp[index][capacity] = zeroOneKnapsackRec(index-1,wt,val,capacity)
            return dp[index][capacity]
        else:
            dp[index][capacity] =  max(val[index-1] \
                        + zeroOneKnapsackRec(index-1,wt,val,capacity-wt[index-1]) ,\
                                zeroOneKnapsackRec(index-1,wt,val,capacity-wt[index-1]))
                                       
            return dp[index][capacity]

zeroOneKnapsackMemoization(len(wt),wt,val,capacity)
``` 
**Output:** 220



```
def topDownKnapsack(wt,val,capacity):
    dp = [[0 for i in range(capacity+1)] for j in range(len(wt)+1)]
    for i in range(len(wt)+1):
        for j in range(capacity+1):
            if i == 0 or j == 0:
                dp[i][j] = 0
            elif wt[i-1] <= j:
                dp[i][j] = max(
                    val[i - 1] + dp[i - 1][j - wt[i - 1]],
                               dp[i - 1][j])      
            else:
                 dp[i][j] = dp[i - 1][j]
                      
    return dp

print("ans :",topDownKnapsack(wt,val,capacity)[len(wt)][capacity])

# to see dp table
from pandas import *
matrix = topDownKnapsack(wt,val,capacity)
df = DataFrame(matrix)
print(df)
``` 
**Output:** ans : 220

Table formed :

```
	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31	32	33	34	35	36	37	38	39	40	41	42	43	44	45	46	47	48	49	50
0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1	0	0	0	0	0	0	0	0	0	0	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60
2	0	0	0	0	0	0	0	0	0	0	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	100
3	0	0	0	0	0	0	0	0	0	0	60	60	60	60	60	60	60	60	60	60	100	100	100	100	100	100	100	100	100	100	160	160	160	160	160	160	160	160	160	160	160	160	160	160	160	160	160	160	160	160	160
4	0	0	0	0	0	0	0	0	0	0	60	60	60	60	60	60	60	60	60	60	100	100	100	100	100	100	100	100	100	100	160	160	160	160	160	160	160	160	160	160	180	180	180	180	180	180	180	180	180	180	220
``` 

## Unbounded Knapsack (Repetition of items allowed)

```
def recursiveUnboundedKnapsack(val, wt, W, n):
    """
    W = capacity,
    n = index
    """
    if n == 0 or W == 0:
        return 0
    elif wt[n - 1] > W:
        return recursiveUnboundedKnapsack(val, wt, W, n-1)
    else:
        return max(
            val[n - 1] + recursiveUnboundedKnapsack(val, wt, W - wt[n - 1], n),
            recursiveUnboundedKnapsack(val, wt, W, n-1),
        )
print(recursiveUnboundedKnapsack(val, wt, capacity, len(wt)))
``` 

**Output:** 300


```
def unboundedKnapsackDp(val, wt, W, n):
    """
    W = capacity,
    n = index
    """
    dp = [[0 for _ in range(W + 1)] for _ in range(n + 1)]

    for i in range(n + 1):
        for j in range(W + 1):
            if i == 0 or j == 0:
                dp[i][j] = 0
            elif wt[i - 1] > j:
                dp[i][j] = dp[i - 1][j]
            else:
                dp[i][j] = max(val[i - 1] + dp[i][j - wt[i - 1]], dp[i - 1][j])
    return dp

print("ans :",unboundedKnapsackDp(val, wt, capacity, len(wt))[len(wt)][capacity])

# to see dp table
from pandas import *
matrix = unboundedKnapsackDp(val, wt, capacity, len(wt))
df = DataFrame(matrix)
print(df)
``` 
**Output:** ans : 300
Table formed :

```
	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31	32	33	34	35	36	37	38	39	40	41	42	43	44	45	46	47	48	49	50
0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1	0	0	0	0	0	0	0	0	0	0	60	60	60	60	60	60	60	60	60	60	120	120	120	120	120	120	120	120	120	120	180	180	180	180	180	180	180	180	180	180	240	240	240	240	240	240	240	240	240	240	300
2	0	0	0	0	0	0	0	0	0	0	60	60	60	60	60	60	60	60	60	60	120	120	120	120	120	120	120	120	120	120	180	180	180	180	180	180	180	180	180	180	240	240	240	240	240	240	240	240	240	240	300
3	0	0	0	0	0	0	0	0	0	0	60	60	60	60	60	60	60	60	60	60	120	120	120	120	120	120	120	120	120	120	180	180	180	180	180	180	180	180	180	180	240	240	240	240	240	240	240	240	240	240	300
4	0	0	0	0	0	0	0	0	0	0	60	60	60	60	60	60	60	60	60	60	120	120	120	120	120	120	120	120	120	120	180	180	180	180	180	180	180	180	180	180	240	240	240	240	240	240	240	240	240	240	300

``` 

 ## fractional knapsack problem (greedy  approach)


```
class item(object):
    """ class to store item """
    def __init__(self,wt,val,index):
        self.wt = wt
        self.val = val
        self.index = index
        self.cost = val // wt
    def __lt__(self, other):
        return self.cost < other.cost

class build_item_list:
    """ class to build item list """
    def __init__(self,wt_list,val_list):
        self.wt_list = wt_list
        self.val_list = val_list
    def build(self):
        item_list = []
        for index in range(len(self.wt_list)):
            item_list.append(item(self.wt_list[index],self.val_list[index],index))
        return item_list

class FractionalKnapSack(object):
    """ knapsack sol class """
    def __init__(self,wt_list,val_list,capacity):
        # Builder design pattern
        self.item_list = build_item_list(wt_list,val_list).build()
        self.capacity = capacity
        self.totalValue = 0
        self.totalValue = self.getMaxValue()   
        
    def getMaxValue(self):
        """ function return max val a knapsack can hold"""
        self.item_list.sort(reverse=True)
        for i in self.item_list:
            curWt = int(i.wt)
            curVal = int(i.val)
            if self.capacity - curWt >= 0:
                self.capacity -= curWt
                self.totalValue += curVal
            else:
                fraction = self.capacity / curWt
                self.totalValue += curVal * fraction
                self.capacity = int(self.capacity - (curWt * fraction))
                break
        return self.totalValue
    
    def __repr__(self):
        return f" Total value of knapsack is {self.totalValue}"
    
    def __str__(self):
        return f" Total value of knapsack is {self.totalValue}"

print(FractionalKnapSack(wt,val,capacity))
``` 
**Output:** Total value of knapsack is 240.0