Search This Blog

#include<stdio.h>
#include<conio.h>
 int sum=0;
 int max(int a,int b)
 {
  if(a>b)
   return a;
  else
   return b;
 }
 void knapsack(int m,int n,int w[],int p[])
 {
 int v[100][200],x[10],i,j;
 for(j=0;j<=m;j++)
  v[0][j]=0;
   for(i=1;i<=n;i++)
   {
    for(j=0;j<=m;j++)
    {
    if(j>=w[i])
     v[i][j]=max(v[i-1][j],v[i-1][j-w[i]]+p[i]);
    else
     v[i][j]=v[i-1][j];
    }
   }
   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("\nTHE OPTIMAL SET OF WEIGHTS IS:\n");
 for(i=1;i<=n;i++)
  {
   if(x[i]==1)
    {
    printf("X%d=1\t",i);
    sum=sum+p[i];
    }
   else
    printf("x%d=0\t",i);
  }
  printf("\nTotal profit = %d",sum);
  }
void main()
{
int w[10],p[10],i,m,n;
printf("\t0/1 KNAPSACK PROBLEM\n\n");
printf("ENTER THE NUMBER OF ITEMS: ");
scanf("%d",&n);
printf("ENTER THE WEIGHTS OF THE ITEMS:\n");
for(i=1;i<=n;i++)
scanf("%d",&w[i]);
printf("ENTER THE PROFITS OF THE ITEMS:\n");
for(i=1;i<=n;i++)
scanf("%d",&p[i]);
printf("ENTER THE CAPACITY OF KNAPSACK: ");
scanf("%d",&m);
knapsack(m,n,w,p);
getch();
}
/*
        0/1 KNAPSACK PROBLEM

ENTER THE NUMBER OF ITEMS: 5
ENTER THE WEIGHTS OF THE ITEMS:
2
3
4
5
6
ENTER THE PROFITS OF THE ITEMS:
3
4
5
6
7
ENTER THE CAPACITY OF KNAPSACK: 8

THE OPTIMAL SET OF WEIGHTS IS:
x1=0    X2=1    x3=0    X4=1    x5=0
Total profit = 10
*/

No comments

Powered by Blogger.