Question

C Program: (Knapsack Exhaustive): How do I add the 5 random generated values into the val [] arrays and how to add the total maximum weights ?

   // 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 knapSackExhaustive(int W, int wt[], int val[], int n){
  

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
if (wt[n-1] > W)
return knapSackExhaustive(W, wt, val, n-1);

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

}
  

int main() {
  
  
int i;
time_t t;


//Intializes random number generator
srand((unsigned) time(&t));

// Print 5 random values from 3 to 15
int q;
printf("Five Random Values:\n");
for( i = 0 ; i < 5 ; i++ ) {
int q=printf(" %d\n",rand() % 15+2);
}
int val[]= {i};

   int j;
   //Print 5 random weights from 1 and 10000
   printf("Five Random Weights:\n");
for( j = 0 ; j < 5 ; j++ ) {
printf(" %d\n", rand() % 10000);
}

int wt[]={j};

  
int W = 10000;
int n = sizeof(val)/sizeof(val[0]);
n = sizeof(wt)/sizeof(wt[0]);
  
printf("Total Value: %d\t\n", knapSackExhaustive(W, wt, val, n));

printf("Total Weight:\t");

return 0;
}

Answer 1

Program:

#include <stdio.h>

#include <stdlib.h>

#include <time.h>

// 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 knapSackExhaustive(int W, int wt[], int val[], int n){

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

if (wt[n-1] > W)

return knapSackExhaustive(W, wt, val, n-1);

else return max( val[n-1] + knapSackExhaustive(W-wt[n-1], wt, val, n-1),

knapSackExhaustive(W, wt, val, n-1)

);

}

int main() {

int i;

time_t t;

int val[5] ; // Intialises random number generator

srand((unsigned) time(&t));

// Print 5 random values from 3 to 15

printf("Five Random Values:\n");

for( i = 0 ; i < 5 ; i++ ) {

val[i] = rand() % 12+3; // It generate random numbers between 3 to 15 where rand() % 12 generate 0 to 12 so need to add 3

printf("%d\n",val[i]);

}

int j;

int wt[5] ;

//Print 5 random weights from 1 and 10000

printf("Five Random Weights:\n");

for( j = 0 ; j < 5 ; j++ ) {

wt[j] = rand() % 10000+1; // It generate random numbers between 1 to 100 where rand() % 1000 generate 0 to 999 so need to add 1

printf("%d\n",wt[j]);

}

int W = 10000;

int n = sizeof(val)/sizeof(val[0]);

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

int totWt=0;

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

totWt = totWt+wt[i];

printf("Total Value: %d\t\n", knapSackExhaustive(W, wt, val, n));

printf("Total Weight: %d\t",totWt);

return 0;

}

Output: