KnapSack Problem

ALGORITHM Knapsack(i, j)

//Implements the memory function method for the knapsack problem
//Input: A nonnegative integeri indicating the number of the first
// items being considered and a nonnegative integer j indicating
 the knapsack capacity
//Output: The value of an optimal feasible subset of the firsti items
//Note: Uses as global variables input arraysW eights[1..n], V alues[1..n],
//and table F [0..n, 0..W] whose entries are initialized with -1’s except for
//row 0 and column 0 initialized with 0’s


if F [i, j] < 0

if j < Weights[i]
value ← Knapsack(i - 1, j)


else 
value ← max(Knapsack(i - 1, j),


Values[i] + Knapsack(i - 1, j - Weights[i]))

F [i, j] ← value


return F [i, j] 

C program:

#include<stdio.h>
int high=0,low=0,ma=0;
int max(int a, int b)
 { return (a > b)? a : b; }


int knapSack(int W, int wt[], int val[], int n)

{
   int i, w;

   int K[n+1][W+1];


   for (i = 0; i <= n; i++)

  {

  for (w = 0; w <= W; w++)

  {

    if (i==0 || w==0)

            K[i][w] = 0;

        else if (wt[i-1] <= w)
             {
                 K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]],  K[i-1][w]);
            }
           else{

 K[i][w] = K[i-1][w];
  }
 if(K[i][w]>ma)
               {
                   ma=K[i][w];
                   high=i;
               }

  }
  }


  return K[n][W];

}


int main()

{

   int i,a,n, val[20], wt[20], W;


    printf("Enter number of items:");

  scanf("%d", &n);

   for(i = 0;i < n; ++i)
{
printf("Enter value  of items %d:\n",i+1);
        scanf("%d", &val[i]);
printf("Enter weight  of items %d:\n",i+1);
scanf("%d",&wt[i]);
    }


printf("Enter size of knapsack:");

 scanf("%d", &W);
printf("-------------------------\n");
printf("|Item no| value  |Weight|\n");
 for(i=0;i<n;i++)
 {
printf("|%d      |%d       |%d     |\n",i+1,val[i],wt[i]);

 }
printf("-------------------------\n");

int value=knapSack(W, wt, val, n);
a=value-val[high];
    printf("the total valued gained in knapSack=%d\n", value);
 for(i = 0;i < n; ++i)
{
 if(a==val[i])
 {
     low=i;
break;
  }
}
    printf("%d %d",high,low+1);
      return 0;

}


Output:

Enter number of items:4
Enter value  of items 1:
20
Enter weight  of items 1:
2
Enter value  of items 2:
30
Enter weight  of items 2:
3
Enter value  of items 3:
40
Enter weight  of items 3:
4
Enter value  of items 4:
50
Enter weight  of items 4:
5
Enter size of knapsack:5
-------------------------
|Item no| value  |Weight|
|1      |20       |2     |
|2      |30       |3     |
|3      |40       |4     |
|4      |50       |5     |
-------------------------
the total valued gained in knapSack=50
2 1