Knapsack - Unable To Understand a Section While Programming

Question

Recently, I am trying to study and implement the Knapsack problem (That I studied few years earlier). So I can understand and have the idea of optimal solution like if the knapsack value is 100 and there are certain weights like 40, 60, 100. Then the optimal solution would be 100 to fill in or equivalent of knapsack value. I stuck in one section of the programming and unable to figure out how this is actually working though tried with recursion using a tutorial. Let me comment out that I've understood:

/*A function or method to determine the max number*/
int max(int a, int b)
{
    return (a > b) ? a : b;
}

/*Knapsack function or method with parameters knapsack value - w, weights, amounts, number of elements*/
int Knapsack(int w, int weight[], int amt[], int n)
{
    if(n == 0 || w == 0)
    {
        return 0;
    }

    if(weight[n - 1] > w) /*If the nth value is greater than the knapsack value, then there will no optimal solution*/
    {
        return Knapsack(w, weight, amt, n - 1);
    }
    else
    {
        return max(amt[n - 1] + Knapsack(w - weight[n - 1], weight, amt, n - 1), Knapsack(w, weight, amt, n - 1)); /*Stuck in this section - It returns perfect solution but unable to understand how it's working. Debugged not getting the answer as expected*/
    }
}

int main(void)
{
    int amt[3], weight[3], w, i, elements, n;

    /*printf("Enter number of elements: ");
    scanf("%d", &elements);*/

    printf("Enter the weight and amount individually up to 3: ");

    for(i = 0; i < 3; i++)
    {
        scanf("%d %d", &weight[i], &amt[i]);
    }

    printf("\nEnter the knapsack value: ");
    scanf("%d", &w);

    n = sizeof(amt) / sizeof(amt[0]);

    printf("%d %d", Knapsack(w, weight, amt, n), n);

    return 0;
}

I would appreciate if someone has the time to explain in brief the working procedure in the programming that I am unable to understand. Even trying to use Dynamic programming for it. But it seems quiet complex. Is this a perfect solution to study knapsack problem:

Knapsack Problem

Answer 1

I have tried to draw a tree structure for the order of calls that would take place once User has Entered all the Weight, Amount, w values.

Here in my example, Following are the values for variables,

Weight[0]=18 Amount[0]=17 Weight[1]=14 Amount[1]=15 Weight[2]=15 Amount[2]=10

W=20(knapsack capacity) Here value of n according to program would be 3.

For the First call from main, Value will be K(w, W[], a[], n)====>K(20,w[], a[], 3) then a[n-1]==>a[2]==>10 w[n-1]==>w[2]==>15 and so on... values change

Note : Keep in Mind the Value Changes after function is called each time. Also keep a tab on IF conditions.

Please ignore handwriting. Thanks.

When we are dealing with Recursion problem, We need to remember that we are dealing with STACK and therefore LIFO( Last In First Out).

In case of recursive functions, the function that is called Last will return result first and function called First will return result at last. Your problem does that if you see tree structure you would understand it. Thanks.

Answer 2

The program for napsack is
note:This program assumes that we can also take fraction of some items.

#include<stdio.h>
void quick(float a[],float b[],float c[],int l,int u)        //quick(array ref, starting index, end index);
{
   float p,temp;int i,j;
   if(l<u)
   {
   p=a[l];
   i=l;
   j=u;
    while(i<j)
   {
      while(a[i] <= p && i<j )      //chane for desc
     i++;
      while(a[j]>p && i<=j )       //change for desc
       j--;
      if(i<=j)
      {
      temp=a[i];
      a[i]=a[j];
      a[j]=temp;
      temp=b[i];
      b[i]=b[j];
      b[j]=temp;
      temp=c[i];
      c[i]=c[j];
      c[j]=temp;
      }
  }
  temp=a[j];
  a[j]=a[l];
  a[l]=temp;
   temp=b[j];
  b[j]=b[l];
  b[l]=temp;
  temp=c[j];
  c[j]=c[l];
  c[l]=temp;

  quick(a,b,c,l,j-1);
  quick(a,b,c,j+1,u); 
 }
}

int main()
{
    int t,i;
    float p=0,w,cc;
    printf("Enter number of elements :");
    scanf("%d",&t);
    printf("Enter maximum allowed weight :");
    scanf("%d",&w);
    float a[t],b[t],c[t];
    printf("Enter weights :");
    for(i=0;i<t;i++)
    scanf("%f",&a[i]);
    printf("Enter profits :");
    for(i=0;i<t;i++)
    {
        scanf("%f",&b[i]);
        c[i]=b[i]/a[i];
    }


    quick(c,a,b,0,t-1);



    cc=0;
    for(i=t-1;i>=0;i--)
    {
        if(cc>=w)
        break;

        if(cc+a[i]<=w)
        {
            p+=b[i];
            cc+=a[i];
        }
        else
        {

            p+=b[i]*(w-cc)/a[i];
            cc+=a[i];
            break;
        }
    }
    printf("Maximum profit %f",p);

}

What i am doing is, first find the profit/weight for each item and save it in a array.
Sort this array.
Then select the item with maximum profit/weight, add it to the sack.
Then move to next item with maximum profit/weight and add it to the sack.
Continue doing this until the sack is full.