knapsack.c

#include<iostream.h>
#include<stdio.h>
#include<conio.h>
int w[10],p[10],v[10][10],s[10],wt,m,n,i,j;
void knapsack()
{
 cout<<"\n Enter the no of weights:\t";cin>>n;m=n;
 cout<<"\n Enter the weights :\t";
 for(i=1;i<=n;i++) scanf("%d",&w[i]);
 cout<<"\n Enter the price of these weights:\t";
 for(i=1;i<=n;i++) scanf("%d",&p[i]);
 cout<<"\n Enter the weights to be optimized:\t";cin>>wt;
 //creating the solution matrix..................
 for(i=1;i<=n;i++)
 for(j=1;j<=wt;j++)
  if(j-w[i]>=0)
    v[i][j]=v[i-1][j]>(v[i-1][j-w[i]]+p[i])?v[i-1][j]:(v[i-1][j-w[i]]+p[i]);
  else
    v[i][j]=v[i-1][j];

 //tracking back the optimal solution vector.........................
 while(n>=1)
 {
  if(v[n][wt]!=v[n-1][wt])
    {
      s[n]=1;
      wt=wt-w[n];
    }
  n--;
 }
 cout<<"\n Optimal solution vector:\t{ ";
 for(i=1;i<m;i++)
  cout<<s[i]<<" , ";
 cout<<s[m]<<" }";
 }

 void main()
 {
  clrscr();
  knapsack();
  getch();
 }