LetUsCPlusPlus/KNAPSACK.CPP at main · Balaji4/LetUsCPlusPlus · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include<stdio.h>
#include<conio.h>
#include<iostream.h>
class knap
{
int n,m,v[10][10],p[10],w[10];
public:void read();
       void opt();
       void write();
};
void knap::read()
{
cout<<"Enter the number of objects"<<endl;
cin>>n;
cout<<"Enter the weights of the objectd"<<endl;
for(int i=1;i<=n;i++)
cin>>w[i];
cout<<"enter the profits of the objects"<<endl;
for( i=1;i<=n;i++)
cin>>p[i];
cout<<"enter the capacity of knapsack"<<endl;
cin>>m;
}

void knap::write()
{
int i,j,x[10];
cout<<"output is"<<endl;
for(i=0;i<=n;i++)
{
 for(j=0;j<=m;j++)
 {
  cout<<" "<<v[i][j];
 }
 cout<<endl;
}
cout<<"optimal solution is"<<v[n][m]<<endl;
for(i=0;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=i-1;
 }
 for(i=1;i<=n;i++)
 {
 cout<<"X["<<i<<"]";
 }
 cout<<"=";

 for(i=1;i<=n;i++)
 {
 cout<<" "<<x[i]<<" ";
 }
}
 int max(int a,int b)
 {
 return a>b?a:b;
 }
 void knap::opt()
 {
 for(int i=0;i<=n;i++)
 {
  for(int j=0;j<=m;j++)
  {
  if(i==0||j==0)
   v[i][j]=0;
   else if(j<w[i])
   v[i][j]=v[i-1][j];
   else
   v[i][j]=max(v[i-1][j],v[i-1][j-w[i]]+p[i]);
   }}}


 void main()
{
knap a;
clrscr();
a.read();
a.opt();
a.write();
getch();
}