Update the given 0-1 or binary knapsack program to minimize no. of columns approximately equal or in order of number of inputs having very large knapsack capacity. program to be updated: #include #include void display(int B[5][6]); void main() { int b[]={3,4,5,6}; // 1D array to hold benefit of items int wt[]={2,3,4,5}; // 1D array to hold weight of items int B[5][6];
Update the given 0-1 or binary knapsack program to minimize no. of columns approximately equal or in order of number of inputs having very large knapsack capacity.
program to be updated:
#include<stdio.h>
#include<conio.h>
void display(int B[5][6]);
void main()
{
int b[]={3,4,5,6}; // 1D array to hold benefit of items
int wt[]={2,3,4,5}; // 1D array to hold weight of items
int B[5][6];
int MaxCapacity=5; //total capacity of knapsack
int n=4; //no. Of items
int wi,bi; // weight and benefit of item i
for(int i=0;i<=n;i++)
{
B[i][0]=0; // first col is assigned 0 as no benefit if current Capacity (w) =0
}
for(int w=0;w<=MaxCapacity;w++)
{
B[0][w]=0; // first row is assigned 0 as no benefit if no. Of items=0
}
for(i=1;i<=4;i++)
{
for(w=1;w<=5;w++)
{
B[i][w]=-1;
}
}
printf("\n initially benefit matrix B is as follows after 1st row n col is 0 \n");
display(B);
for(i=1;i<=4;i++)
{
wi=wt[i-1];bi=b[i-1]; // weight and benefit of item i
for(int w=1;w<=5;w++)
{
if(w<wi) //current knapsack capacity ' w' is smaller then ItemWeight ' wi'
{
B[i][w]=B[i-1][w]; // item i can't be included in knapsack
printf("\n item %d can't be included in knapsack as current knapsack capacity %d is smaller then ItemWeight %d ",i,w,wi) ;
printf("\nouter if B[%d][%d]= %d",i,w,B[i][w]);
}
else // item i can be included in knapsack but check for greater benefit
{
if((bi+B[i-1][w-wi]) > (B[i-1][w]))
{ // inclusion of item give greater benefit
B[i][w]=bi+B[i-1][w-wi];
printf("\n inclusion of item %d give greater benefit ",i) ;
printf("\ninner if B[%d][%d]= %d",i,w,B[i][w]);
}
else // exclusion of item give greater benefit i. e. Benefit from above cell
{
B[i][w]=B[i-1][w];
printf("\n exclusion of item %d give greater benefit ",i) ;
printf("\ninner else B[%d][%d]= %d",i,w,B[i][w]);
}
}
}
}
printf("\n complete solution for benefit matrix B \n");
display(B);
getch();
}
void display(int B[5][6])
{
for(int i=0;i<=4;i++)
{
printf("\n");
for(int w=0;w<=5;w++)
{
printf("\t%d",B[i][w]);
getch();
}
}
}
in C language
thanks a lot in advance:)
Step by step
Solved in 3 steps with 2 images
