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