Question

C Program: How do I write a Greedy function for 0-1 knapsack, to find total value only( replace struct Knapsack)

# include
#include
#include

struct Knapsack {
   int value;
   int weight;
};

   // 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
   struct Knapsack knapSackExhaustive(int W, int wt[], int val[], int n){
   int i, w;
   int K[n+1][W+1];
   int totalWeight=0;

   // Build table K[][] in bottom up manner

   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];
   }
  
   }
  
   //For calculation of totalweight;
   int res = K[n][W];   
  
   w = W;
  
   for (i = n; i > 0 && res > 0; i--) {
   // either the result comes from the top
   // (K[i-1][w]) or from (val[i-1] + K[i-1]
   // [w-wt[i-1]]) as in Knapsack table. If
   // it comes from the latter one/ it means
   // the item is included.
   if (res == K[i - 1][w])
  
   continue;   
  
   else {
   // This item is included.
   //printf("%d ", wt[i - 1]);
  
   totalWeight=totalWeight+wt[i-1];
  
   // Since this weight is included its
   // value is deducted
      
   res = res - val[i - 1];
  
   w = w - wt[i - 1];
   }
}

   struct Knapsack knap;
   knap.value=K[n][W];
   knap.weight=totalWeight;
   return knap;
}// end struct knapSackExhaustive

int main(void) {
  
   struct Knapsack aSack;  
   int i;
   time_t t;
   int val[5];
   int wt[5];
  
   //Intializes 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()%15+3;
   printf("%d\n",val[i]);
  
}
  
   int j;
   //Print 5 random weights from 1 and 10000
   printf("Five Random Weights:\n");
   for( j = 0 ; j < 5 ; j++ ) {
   wt[j]=rand() % 10000;
   printf(" %d\n", wt[j]);
  
}

   int W = 10000;
   int n = sizeof(val)/sizeof(val[0]);
  
   aSack = knapSackExhaustive(W, wt, val, n);

   printf("Total Value: %d\t\n", aSack.value);
   printf("Total Weight:%d\t",aSack.weight);
  
   return 0;
}

Answer 1

GREEDY APPROACH FOR 0/1 KNAPSACK PROBLEM

#include<stdio.h>

int main() {

int wt[5]={0,2,3,4,5};//weight of different items
int b[5]={0,3,4,5,6};//corresponding benefit(profit/value) related to that particular item
//b[i] is the benefit of item having weight wt[i]
//0 is placed at starting of weight and benefit array because in the below nested loop i will go from 1 to 4 so b[4] will be benefit of 4th item which then create error as no index will be available
int W=5;//total weight of bag available
int n=4;//number of items
int i,w;
int v[n+1][W+1];
for(w=0;w<W+1;w++)
{v[0][w]=0;
}
for(i=0;i<n+1;i++)
{
v[i][0]=0;
}
for(i=1;i<=n;i++)
{
for(w=1;w<=W;w++)
{
if(wt[i]<=w)//that means items can be a part of the bag
{
if((b[i]+v[i-1][w-wt[i]])>v[i-1][w])
{
v[i][w]=v[i-1][w-wt[i]]+b[i];
  
}
else
v[i][w]=v[i-1][w];
}
else
{
v[i][w]=v[i-1][w];
  
}
}
}
for(i=0;i<=n;i++)
{
for(w=0;w<=W;w++)
{
printf("%d ",v[i][w]);
}
printf("\n");
}
  
printf("benefit =%d",v[n][W]);
  
  
}