Question

Write a program that solves the Knapsack problem. Code to the following standards.

Your source of items to put into the knapsack should consist of five randomly generated integers in the range of 1 to 20.

Your knapsack can hold 20 lbs.

Answer 1

/* implementation of 0-1 Knapsack problem */
#include<stdio.h>
#include <time.h>
#include <stdlib.h>

// A utility function that returns maximum of two integers
int max(int a, int b) { return (a > b)? a : b; }

// Returns the maximum value that can be put in a knapsack of capacity W
int knapSack(int W, int wt[], int val[], int n)
{
// Base Case
if (n == 0 || W == 0)
   return 0;

// If weight of the nth item is more than Knapsack capacity W, then
// this item cannot be included in the optimal solution
if (wt[n-1] > W)
   return knapSack(W, wt, val, n-1);

else return max( val[n-1] + knapSack(W-wt[n-1], wt, val, n-1),
                   knapSack(W, wt, val, n-1)
               );
}

int main()
{
int n;
printf("Enter the number of element between 0 to 5");
scanf("%d",&n);
int val[n];
int wt[n];
  
for(int i=0;i<n;i++)
{
val[i]=rand()%5;  
   }
   for(int i=0;i<n;i++)
   {
      wt[i]=rand()%5;
   }
   int W = 20;
   printf("%d", knapSack(W, wt, val, n));
   return 0;
}