mercredi 1 juillet 2020

Lowest level of the recursion tree for the knapsack problem

I am having a hard time understanding how the knapsack problem is able to return the right values. I understand that when the weight is within the limits, we have a choice to either include the item or not include the item into our knapsack.

Can someone explain what happens at the lowest level of the recursion tree?

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

int main()
{
    int wt[] = {10, 20, 30}; //Weight of each element
    int val[] = { 60, 100, 120};//value of each element
    int w = 50, n = sizeof(val)/sizeof(val[0]); // w is the capacity of the knapsack
    cout<< knapstack(wt, val, w, n);
}

Aucun commentaire:

Enregistrer un commentaire