# Unbounded Knapsack

#### You are given ‘N’ items with certain ‘PROFIT’ and ‘WEIGHT’ and a knapsack with weight capacity ‘W’. You need to fill the knapsack with the items in such a way that you get the maximum profit. You are allowed to take one item multiple times.

##### For Example

```
Let us say we have 'N' = 3 items and a knapsack of capacity 'W' = 10
'PROFIT' = { 5, 11, 13 }
'WEIGHT' = { 2, 4, 6 }
We can fill the knapsack as:
1 item of weight 6 and 1 item of weight 4.
1 item of weight 6 and 2 items of weight 2.
2 items of weight 4 and 1 item of weight 2.
5 items of weight 2.
The maximum profit will be from case 3 i.e ‘27’. Therefore maximum profit = 27.
```

##### Input Format

```
The first line contains a single integer ‘T’ denoting the number of test cases.
The first line of each test contains two integers ‘N’ - number of elements in the array and ‘W’ - Capacity of the knapsack.
The second line of each test case contains profiti - profit of the item at the ‘i-th’ index.
The third line of each test case contains weighti - weight of the item at the ‘i-th’ index
```

##### Output Format

```
For each test case, return an integer denoting the maximum profit that can be obtained by filling the knapsack.
```

##### Note:

```
You do not need to print anything; it has already been taken care of. Just implement the given function.
```

##### Constraints

```
1 <= T <= 50
1 <= N <= 10^3
1 <= W <= 10^3
1 <= PROFIT[ i ] , WEIGHT[ i ] <= 10^8
Time Limit: 1sec
```

A simple idea is to consider all possible sequence of items that have a total weight not more than ‘W’ and find the subset which gives maximum profit.

- For any item at index ‘i’ there will be two choices - either we include the item at least once or we do not include the item.
- If we do not include the item, we will recursively solve for ‘N-1’ items and knapsack capacity ‘W’.
- If we include the item, we will recursively solve for ‘N’ items and capacity = ‘W - weight of Nth item’ and add profit of ‘ N-th’ item to its result as we have included that.
- As we can use any item multiple times, so after including ‘N-th’ item we will still solve for ‘N’ items.
- The maximum value obtained from all these recursive calls will be the required profit.

Algorithm

- Let UNBOUNDED_KNAPSACK( N, W, PROFIT, WEIGHT ) be our recursive function.
- If no item is left or the capacity of the knapsack is 0 i.e. If ( ‘N’ = 0 or ‘W’ = 0), return 0.
- If 'WEIGHT[ N - 1]' > ‘W’ i.e if the weight of the Nth item is greater than the knapsack capacity, we can not include the N-th item. Therefore return UNBOUNDED_KNAPSACK( N - 1, W, PROFIT, WEIGHT ).
- Otherwise, return maximum of the following two values
- If ‘N’-th item is included
- ‘PROFIT’ [ N - 1 ] + UNBOUNDED_KNAPSACK( N, W - WEIGHT [ N - 1 ] , PROFIT, WEIGHT )

- If N-th item is not included
- UNBOUNDED_KNAPSACK( N - 1, W, PROFIT, WEIGHT ).

- If ‘N’-th item is included

In the recursive approach, some problems are solved again and again.

Let us see a recursion tree for ‘W’ =7, ‘N’ = 4 , 'PROFIT' =[1,6,10,16], ‘WEIGHT’ = [1,2,3,5].

It is clear from the recursion tree that the problem for ‘N’ = 1 and ‘W’ = 5 is solved for two times.

The recursive approach can be optimized by maintaining an extra 2-d array **‘RES’ **that stores the result of the recursive calls. For every sub-problem, we first check the 'RES' array. If the value is already computed we simply return it otherwise we calculate it using recursion and put it in the “res” array.

Algorithm

- Initialize a 2-D array ‘RES’ of ‘ W+1’ rows and ‘N + 1’ columns and initialize its values to -1.
- If ( RES [ W ][ N ] ! = -1 ), return RES [ W ][ N ].
- If ( N == 0 | | W == 0 ) return res [ W ][ N ] = 0.
- If ( W [ N - 1 ] > W )
- RES [ W ][ N ] = UNBOUNDED_KNAPSACK( N - 1, W, profit, weight ).

- Else
- RES [ W ][ N ] = max ( ( Profit [ N - 1 ] + UNBOUNDED_KNAPSACK( N, W - weight [ N - 1 ] , profit, weight ) UNBOUNDED_KNAPSACK( N - 1, W, profit, weight ) ).

- Return res [ W ][ N ].

We will solve the problem in a bottom-up manner. We will compute the result for all values of knapsack capacity from 0 to W. We will maintain a 1-D array ‘DP’ of size ‘W+1’ with all its initial values as 0. ‘DP[ i ]’ stores the maximum profit that can be obtained by using all items and knapsack capacity ‘ i ‘.

For every value of ‘ i ‘, we will check for all items. If the weight of any item at index ‘ j ’ say ‘WEIGHT[ j ]’ is smaller than current knapsack capacity i.e ‘ i ’, that means we can include that item, and ‘DP[ i ]’ will be max ( DP[ i ], PROFIT [ j ] + profit when knapsack capacity = i - WEIGHT[ j ].)

DP [ W ] will store the required answer.

Algorithm

- Initialize a 1-D array ‘DP’ of size ‘W+1’ with all values = 0.
- Run two loops
- ‘i’ : 0 to ‘W’
- ‘j’ : 0 to ‘N-1’
- If ( ‘WEIGHT [ j ]’ < = i ) , DP [ i ] = max (DP [ i ] , PROFIT [ j ] + DP[ i - WEIGHT[ j ] )

- Return DP[ W ].