Scribd
Upload
11 views3 pages

Dknap

The document contains a C program that implements the dynamic programming solution for the 0/1 Knapsack problem. It defines functions to calculate the maximum profit that can be obtained given a set of items with specific weights and profits, and a knapsack with a defined capacity. The program prompts the user for the number of items, their weights, profits, and the knapsack's capacity, then outputs the optimal solution and the solution vector.

Uploaded by

kp.gamer.879287
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
11 views3 pages

Dknap

The document contains a C program that implements the dynamic programming solution for the 0/1 Knapsack problem. It defines functions to calculate the maximum profit that can be obtained given a set of items with specific weights and profits, and a knapsack with a defined capacity. The program prompts the user for the number of items, their weights, profits, and the knapsack's capacity, then outputs the optimal solution and the solution vector.

Uploaded by

kp.gamer.879287
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 3

#include<stdio.

h>
int i,j,n,m,p[10],w[10],v[10][10];
int max(int x,int y)
{
if(x>y)
return x;
else
return y;
}
void Dknapsack()
{
int x[10];
for(i=0;i<=n;i++)
{
for(j=0;j<=m;j++)
{
if(i==0||j==0)
{
v[i][j]=0;
}
else if(j-w[i]<0)
{
v[i][j]=v[i-1][j];
}
else
{
v[i][j]=max(v[i-1][j],v[i-1][j-w[i]]+p[i]);
}
}
}
printf("\n the output is:\n");
for(i=0;i<=n;i++)
{
for(j=0;j<=m;j++)
{
printf("%d\t",v[i][j]);
}
printf("\n\n");
}
printf("\n the optimal solution is %d",v[n][m]);
printf("\n the solution vector is:\n");
for(i=n;i>=1;i--)
{
if(v[i][m]!=v[i-1][m])
{
x[i]=1;
m=m-w[i];
}
else
{
x[i]=0;
}
}
for(i=1;i<=n;i++)
{
printf("%d\t",x[i]);
}
}
void main()
{
printf("\n enter the no. of items:\t");
scanf("%d",&n);
printf("\n enter the weight of the each item:\n");
for(i=1;i<=n;i++)
{
scanf("%d",&w[i]);
}
printf("\n enter the profit of each item:\n");
for(i=1;i<=n;i++)
{
scanf("%d",&p[i]);
}
printf("\n enter the knapsack's capacity:\t");
scanf("%d",&m);
Dknapsack();
}

You might also like