🙏

জয়  শ্রী  রাম

🕉

---

Similar Other Concept:

• Classical 0/1 Knapsack Problem

Unbounded Knapsack Problem:

Given a Knapsack of weight limit W and a set of n items with certain value val_i and weight wt_i, Suppose I have infinite copies of all of the items. What’s the most valuable way to fill the knapsack maintaining the maximum weight constraint of the knapsack ?

Examples:
Input :
W = 1000
val[] = {1, 30}
wt[] = {10, 500}
Output : 100

There are many ways to fill knapsack.
1) 2 instances of 500 unit weight item.
2)1 instance of 500 unit weight item and 50 instances of 10 unit weight items.
3) 100 instances of 10 unit weight item.


We get maximum value with option 3.

Solution:

We do not have any imposed constraint on how many instances of each item we can use. So for any weight we have two options: (1) we can either include an item (keeping option open to include more than one instances), (2) or do not include it at all (not even one instance), as shown in below recurrence relation:

dp[w] = max(dp[w - weights[i]] + val[i], // include item i
            dp[w]) // do not include item i 
        where i varies from 0 to n-1 such that:
        weights[i] <= w

Result = d[W]
Base case: dp[0] = 0

n = total number of items
W = weight we need to put in knapsack

Code Implementation:

The implementation is simple when we have already gotten the above recurrence relation. We will go on computing the result for max weights in its increasing order (max weight = 0 to W) so that while calculating higher order of max weight we can use the already computed dp value for the lower order of the max weight (optimal substructure property of Dynamic Programming). In the above recurrence relation we see that when we are including item i we get dp[w] = dp[w - weights[i]] + val[i] , so while calculating dp result for max weight w, we would need the dp value of max weight (w - weights[i]). This is exactly what we have implemented below:

Java code:



Login to Access Content




Python Code:



Login to Access Content



Important to note, for most problems the order in which we need to take the outer for loop and inner for loop won't matter, but in some problems having the correct order would be of immense importance. For the problem statement given in this chapter, below two implementation would give the same correct result:

#1.

for(int w = 0; w <= W; w++){ 
            for(int j = 0; j < n; j++){
                    dp[w] = ....
                    ....
    }
}

#2.

for(int i = 0; i < n; i++){ 
            for(int w = 0; w <= W; w++){
                    dp[w] = ....
                    ....
    }
}

It is very important to understand the difference between the above two implementations:

for(int w = 0; w <= W; w++){ 
            for(int j = 0; j < n; j++){
                    dp[w] = ....
                    ....
    }
}

The above implementation means that you are computing value of dp[w = i] for all the items i.e, weights[0...(n - 1)], before jumping on calculating value of dp[w = (i + 1)]. So, here every time we are done with each iteration of calculate dp[w = i] for coin_index = 0 to (n - 1), the value we get for dp[w = i] after the iteration becomes the final final value of dp[w = i] of the sub-problem: "calculate maximum VALUE that the knapsack can carry when maximum knapsack capacity is weight i and the items array is weights[0...(n - 1)] where the original items array is also weights[0...(n - 1)], original given knapsack capacity W where W >= i, and the original final target is T where i <= T".

for(int i = 0; i < n; i++){ 
            for(int w = 0; w <= W; w++){
                    dp[w] = ....
                    ....
    }
}

Whereas in this implementation (above one) we are computing value of dp[w] for all w = 0 to W for item with index = i before jumping on processing item with index = (i + 1). So, here every time we calculate dp[w = j] that becomes the final result for the sub-problem: "calculate the maximum value that the knapsack can carry when maximum knapsack capacity is weight j and the items array is weights[0...current_item_index] which is a subset of the item array given in the original problem". So here when when we are computing dp[w = j] for item with index = i, we are computing dp[j] for items array weights[0...i] and not for the entire array. We get the dp[w = j] for the entire item array weights[0...(n - 1)] only in the last iteration when i = (n - 1).

Try to understand the difference between the above two implementations really well as we would need them in soving various problem. In most simple problems it won't matter which implementation we go with, but for some no-so-trivial problems the order of the outer loop and inner loop would matter, as we would see in Coin Change: Total no. of Combinations Possible.

Bottom-Up Approach with with 2-D Array:

Let dp[i, w] define the maximum value obtainable when we have to put exactly weight w in the knapsack and we have items[0...(i - 1)] as our items and their values as val[0...(i - 1)] and their weights weights[0...(i - 1)].

For every possible weight w_j we have two options:

1. either, include the item.
   
   dp[i, w] = val[i] + dp[i, w - weights[i]]
   
   Notice in dp[i, w - weights[i]] we have i and NOT i - 1. This keeps our option open to include more than instance of the same item if we want.
   
   
2. or, don't include the item.
   
   In this case we just move on to the next item without including items[i], so the weight w remains the same.
   dp[i, w] = dp[i - 1, w]

At the end, we take the maximum of the value gotten from (1) and (2), as shown below.

dp[i, w] = max(dp[i - 1, w], dp[i, w - weights[i]] + val[i])

Result = dp[n - 1, W], where n = total number of items, W = weight we need to put in knapsack

Base case:
dp[i, 0] = 0, for all i. The maximum value we can get is 0 when we are to put 0 weight in knapsack.

We will discuss the code template for this approach in the below two chapters:

• Coin Change: Minimum no. of Coins
• Coin Change: Total no. of Combinations Possible

Summary:

• Most problems where you need to make up a target sum using unlimited instances of given items, can be solved using Unbounded Knapsack concept.