Trend Posts
Author
View LUQMAN's profile
Showing posts with label Knapsack Dynamic Program. Show all posts
Showing posts with label Knapsack Dynamic Program. Show all posts
Monday, July 21, 2014
/*Implement 0/1 Knapsack problem using DynamicProgramming.*/
#include<stdio.h>
#include<stdlib.h>
int v[100][100],w[100],p[100],x[100],m,n;
void knapsack();
void optimal();
int max(int,int);
void main()
{
int i,j;
printf("\nEnter the number of items:\n");
scanf("%d",&n);
printf("\nEnter the maximum capacity of the bag\n");
scanf("%d",&m);
printf("\nEnter the weight of each item\n");
for(i=1;i<=n;i++)
scanf("%d",&w[i]);
printf("\nEnter the profit of each item:\n");
for(i=1;i<=n;i++)
scanf("%d",&p[i]);
printf("\nITEMS\t\tWEIGHT\t\tPROFIT\n");
for(i=1;i<=n;i++)
printf("%d\t\t%d\t\t%d\n",i,w[i],p[i]);
printf("\n");
knapsack();
optimal();
}
void knapsack()
{
int i,j;
for(i=0;i<=n;i++)
{
for(j=0;j<=m;j++)
{
if(i==0||j==0)
v[i][j]=0;
else if(w[i]>j)
v[i][j]=v[i-1][j];
else
v[i][j]=max(v[i-1][j],p[i]+v[i-1][j-w[i]]);
}
}
printf("\nMaximum profit is:%d",v[n][m]);
}
void optimal()
{
int i,j;
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=i-1;
}
printf("\nThe items possible are:\n");
for(i=1;i<=n;i++)
if(x[i]==1)
printf("%d\t",i);
}
int max(int a,int b)
{
if(a<b)
return b;
else
return a;
}
Subscribe to:
Posts (Atom)