In 01 knapsack fill the table from elements as row or column

#1

Is it better to take elements in the outer loop and run for each sum in inner loop. OR take sum in outer loop and run for elements in inner loop. Can we do this in all variants of knapsack like min coin change problem also? Please explain.

#2

Better way to approach a dynamic programming problem is to first find the recursive relation that may in turn help you in getting the bottom-up filling of the DP table.
Here in 0-1 Knapsack problem ,for each item you have a value and weight associated with it. For a knapsack of a given capacity you have to fill items in it in order to maximize the total value.
So, first thinking recursively in a Top Down manner, you have 2 options at any point-

  1. Either pick up that item only if its weight< capacity of Knapsack
  2. Do not pick up that item
    So you can make recursive call for both the queries and find the maximum among both the queries.In each call modify the left over capacity of the knapsack if you have picked up that item.
    The recursive function would look something like this-
    int knapsack(intweight, int value,int i,int n,int capacity)
    {
    if i==n or capacity==0 //Base Case
    return 0;
    int q1=0;int q2=0;
    if(weight[i]<=capacity) //Means you can pick up the current item at position i
    q1= weight[i]+ knapsack(weight,value,i+1,n,capacity-weight[i]);
    q2=knapsack(weight,value,i+1,n,capacity); //Not picking up that item
    int ans=max(q1,q2);
    return ans;
    }
    You can memoize this using 2D array where i and capacity would be the parameters.

Now the Bottom-up approach;

IMG_20190810_235843-min
IMG_20190810_235843-min4095Ă—3072 896 KB

Here, you will have to fill the table row wise:
if(j<weight[i]) //we cannot pick as including this is exceeding the capacity
dp[i][j]=dp[i-1][j] //best answer excluding the current item
else{
dp[i][j]=max(value[i]+dp[i-1][j-weight[i]],//Including the current item,on including it capacity reduced to j-weight[i]
dp[i-1][j] )//excluding current item
}

#3

Sir, can I take sum as the rows as (i), and the different denomination of coin like 2,4,7 as columns in the MINIMUM number of coins to make sum problem.

#4

Yeah you can do that…but in that case the order of filling the table will change…instead of filling the table row wise, you will have to fill it column wise… Just make the table and try to fill it for both the ways…you will get it clear.

#5

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.