In a Knapsack problem, given n items {I1, I2, · · · , In} with weight {w1, w2, · · · , wn} and value {v1,v2, ···, vn}, the goal is to select a combination of items such that the total value V is maximized and the total weight is less or equal to a given capacity W .
ans)
Here is the code of 0,1 Knapsack problem written in C with output.
/////////////////////////////////////////////////////Code////////////////////////////////////////////////
#include<stdio.h>
#include<conio.h>
void knapsack(int n, int m, int w[], int p[]);
void findknap(int n, int m, int w[], int p[]);
int v[10][10];
void main()
{
int n,i,w[15],p[15],m;
clrscr();
printf("Enter The Number Of Items");
scanf("%d",&n);
printf("enter knapsack wt");
scanf("%d",&m);
printf("Enter The VALUE AND WEIGHT OF ITEM");
for(i=1;i<=n;i++)
{
scanf("%d%d",&p[i],&w[i]);
}
knapsack(n, m, w, p);
findknap(n, m, w, p);
getch();
}
void knapsack(int n, int m, int w[], int p[])
{
int i, j;
for(i=0;i<=n;i++)
v[i][0]=0;
for(j=0;j<=m;j++)
v[0][j]=0;
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
if(j>=w[i])
{
if(v[i-1][j] > v[i-1][j-w[i]]+p[i])
v[i][j]=v[i-1][j];
else
v[i][j]=v[i-1][j-w[i]]+p[i];
}
else
v[i][j]= v[i-1][j];
}
}
for(i=0;i<=n;i++)
{
for(j=0;j<=m;j++)
{
printf("\t%d",v[i][j]);
}
printf("\n");
}
}
void findknap(int n, int m, int w[], int p[])
{
int x[10], i,j, prof=0;
for(i=1;i<=n;i++)
x[i]=0;
i=n;
j=m;
while(i>0 && j>0)
{
if(v[i][j] != v[i-1][j])
{
x[i]=1;
j=j-w[i];
}
i--;
}
printf("\nSelected Item : ");
for(i=1;i<=n;i++)
printf("\t%d",x[i]);
for(i=1;i<=n;i++)
{
prof= prof+(p[i]*x[i]);
}
printf("\nprofit=%d", prof);
}
and
/////////////////////////////////////////////////////Code of Greedy algorithm fractional knapsack problem////////////////////////////////////////////////////
#include<iostream.h>
#include<conio.h>
#include<stdlib.h>
void input(float w[],float v[],int n)
{
int i;
randomize();
for(i=0;i<n;i++)
{
w[i]=rand()%100;
v[i]=rand()%100;
}
cout<<endl;
}
void display(float w[],float v[],float r[],int n)
{
int i;
cout<<"\nWeight\tVolume\tRatio\n";
for(i=0;i<n;i++)
{
cout<<w[i]<<"\t"<<v[i]<<"\t"<<r[i]<<endl;
}
}
void cal(float w[],float v[],float r[],int n,float c)
{
int i,j;
float x[10],k;
for(i=0;i<n;i++)
{
x[i]=0.0;
}
//processing by bubble sort
for(j=0;j<n;j++)
{
for(i=0;i<n-1;i++)
{
if(r[i]<r[i+1])
{
k=r[i]; //swapping of ratio
r[i]=r[i+1];
r[i+1]=k;
k=w[i];
w[i]=w[i+1]; //swapping of weight
w[i+1]=k;
k=v[i];
v[i]=v[i+1]; //swapping of volume
v[i+1]=k;
}
}
}
for(i=0;i<n;i++)
{
if(w[i]>c)
{
break;
}
else
{
x[i]=1.0;
c=c-w[i];
}
}
if(i<=n)
{
x[i]=c/w[i];
}
float sum=0.0;
for(i=0;i<n;i++)
{
x[i]=x[i]*v[i];
sum=sum+x[i];
}
cout<<"\nProfit is : "<<sum;
}
void main()
{
clrscr();
int i,j,n;//c=capacity
float x[10],c,k,w[10],v[10],r[10];
//r=ratio,w=weight,v=volume
cout<<"Enter the maximum value \n";
cin>>n;
input(w,v,n);
cout<<"\nEnter the capacity :\n";
cin>>c;
for(i=0;i<n;i++)
{
r[i]=v[i]/w[i];
}
display(w,v,r,n);
cal(w,v,r,n,c);
getch();
}
////////////////////////////////////////////OUTPUT//////////////////////////////////////////////
///////////////////////////////////////////////////////////
Thank you very much :-)
Keep asking queries
do comment below and please hit like button
Thank you once again :-)
////////////////////////////////////////////////////////////////////
In a Knapsack problem, given n items {I1, I2, · · · , In} with weight {w1, w2, · · · , wn} and value {v1,v2, ···, vn}, the goal is to select a combination of items such that the total value V is maxim...
2 Knapsack Problem In a Knapsack problem, given n items {11, I2, -.., In} with weight {wi, w2, -.., wn) and value fvi, v2, ..., vn], the goal is to select a combination of items such that the total value V is maximized and the total weight is less or equal to a given capacity W. Tt i=1 In this question, we will consider two different ways to represent a solution to the Knapsack problem using an array with size...
solution is required in pseudo code please. 2 Knapsack Problem În al Knapsack problem. given n items(11-12. . . . . 1"} with weight {w1·W2. . . . . ux) and value (n 2, .., nJ, the goal is to select a combination of items such that the total value V is maximized and the total weight is less or equal to a given capacity In this question, we will consider two different ways to represent a solution to the...
For given capacity of knapsack W and n items {i1,i2,...,in} with its own value {v1,v2,...,vn} and weight {w1,w2,...,wn}, find a greedy algorithm that solves fractional knapsack problem, and prove its correctness. And, if you naively use the greedy algorithm to solve 0-1 knapsack problem with no repetition, then the greedy algorithm does not ensure an optimal solution anymore. Give an example that a solution from the greedy algorithm is not an optimal solution for 0-1 knapsack problem.
l have posted it a few times before but didnt get a satisfactory answer. kindly help me by answering in pseudo code 2 Knapsack Problem În al Knapsack problem. given n items(11-12. . . . . 1"} with weight {w1·W2. . . . . ux) and value (n 2, .., nJ, the goal is to select a combination of items such that the total value V is maximized and the total weight is less or equal to a given capacity...
"Greedy, but Better": Given a knapsack problem with a weight capacity C, and n items, and each item has a weight W[1:n] and monetary value P[1:n]. You have to determine which items to take so that the total weight is C, and the total value (profit) is maximized. In this case we are considering an integer problem, so you can either take an item, or not take an item, you cannot take it fractionally. If you recall, the greedy algorithm...
In weighted knapsack problem, given the knapsack capacity is 16 and the following items (Weight, Value), what is the maximum value we can take away. Explain shortly how and by what approach you arrived at this solution. Item 1 (4, 12) Item 2 (3, 14) Item 3 (7, 22) Item 4 (8, 32) Item 5 (4, 24) Item 6 (6, 20)