# Unbounded Knapsack

Posted: 5 Mar, 2021
Difficulty: Moderate

## PROBLEM STATEMENT

#### 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
``````
Approach 1

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 ).