vendredi 3 juillet 2020

Understanding the recursive calls of the knapsack function

I have been trying to understand the knapsack problem and I have gone through lots of explanations.

The problem is that we are given an array of items. Each item has its corresponding weights in the wt array and its corresponding values int the val array. We are also given a max capacity of weight that a bag can hold which is w. We have to add items into our bag in such a way that we can obtain the maximum value and we print the maximum value.

I am still not able to visualize the recursion on the way back up the recursion tree.
I couldn't find any article, video, or visualization of how the recursion works for each of the calls for the knapsack function. I would love it if someone would do that visualization.

int knapsack(int wt[], int val[], int w, int n)
{
    if(n == 0 || w == 0)
        return 0;
    if (wt[n - 1] > w)
        return knapsack(wt,val,w,n-1);
    else
        return max(val[n-1] + knapsack(wt,val, w - wt[n-1],n-1),knapsack(wt, val, w, n-1));
}

int main()
{
    int wt[] = {10, 20, 30};
    int val[] = { 60, 100, 120};
    int w = 50, n = sizeof(val)/sizeof(val[0]);
    cout<< knapsack(wt, val, w, n);
}

I understand why we are making the particular recursive calls, but I am unable to fully understand the step by step process.

Aucun commentaire:

Enregistrer un commentaire