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