Computer Science: 5th sem ADA Lab Program 5

Analysis and Design of Algorithms Lab.

Question 5.

//Implement 0/1 Knapsack problem using dynamic programing

//NOTE: Increase the 'MAX' value to give higher inputs.

#define MAX 10

#include <iostream>

#include <conio.h>

using namespace std;

int sack[MAX][MAX];

inline int bigger(int a,int b)

{

return a>b?a:b;

}

void knapSack(int capacity,int n,int *w,int *v)

{

for(int i=0;i<=n;i++)

{

for(int j=0;j<=capacity;j++)

{

if(i==0 || j==0)

sack[i][j]=0;

else

{

if(j-w[i]>=0)

sack[i][j]=bigger(sack[i-1][j],v[i]+sack[i-1][j-w[i]]);

else

sack[i][j]=sack[i-1][j];

}

}

}

}

void main()

{

cout<<"Enter the capacity of knapsack:";int cap;cin>>cap;

cout<<"Enter the No of items:";int n;cin>>n;

int *value=new int[n+1];

int *weight=new int[n+1];

cout<<"Enter the weight & value of the articles:\nW V\n\n";

for(int i=1;i<=n;i++)

{

cin>>weight[i]>>value[i];

}

cout<<"\nThe knapsack solution:\n";

knapSack(cap,n,weight,value);

for(int i=0;i<=n;i++)

{

for(int j=0;j<=cap;j++)

cout<<sack[i][j]<<"\t";

cout<<"\n";

}

getch();

}