Free Discussion
<![CDATA[
#include<iostream>
#include<conio.h>
#define MAX 10
class knapsack
{
private : int n, capacity, value[MAX][MAX];
struct object
{
int weight;
int value;
} obj[MAX];
public : void getdetails(int &, int &);
void initialise();
int mfknapsack(int, int);
void display(int);
};
void knapsack :: getdetails(int &no, int &cap)
{
int i;
cout << "\nEnter the number of objects : ";
cin >> n;
no = n;
cout << "\nEnter the maximum capacity of the Knapsack : ";
cin >> capacity;
cap = capacity;
cout << "\nEnter the Weights and Values of " << n << " objects\n";
for (i = 1; i <= n; i++)
{
cout << endl;
cout << "Weight[" << i << "] = ";
cin >> obj[i].weight;
cout << "Value[" << i << "] = ";
cin >> obj[i].value;
}
}
void knapsack :: initialise()
{
int i, j;
for (i = 0; i <= n; i++)
for (j = 0; j <= capacity; j++)
{
if (i == 0 || j == 0)
value[i][j] = 0;
else
value[i][j] = -1;
}
}
int knapsack :: mfknapsack(int n, int c)
{
int val, temp, temp1;
if (value[n][c] < 0)
{
temp = mfknapsack(n - 1, c);
if (c < obj[n].weight)
val = temp;
else
{
temp1 = obj[n].value + mfknapsack(n - 1, c - obj[n].weight);
if (temp1 > temp)
val = temp1;
else
val = temp;
}
value[n][c] = val;
}
return (value[n][c]);
}
void knapsack :: display(int cost)
{
int i, next, cap;
cout << "\nThe objects included in the obtimal subset are : ";
next = n;
cap = capacity;
for (i = n; i > 0; i--)
{
if (value[next][cap] != value[next - 1][cap])
{
cout << i << " ";
cap -= obj[i].weight;
}
next = i - 1;
}
cout << "\n\nThe maximum Profit obtained is : ";
cout << cost;
}
int main()
{
clrscr();
int profit, no, cap;
knapsack k;
k.getdetails(no, cap);
k.initialise();
profit = k.mfknapsack(no, cap);
k.display(profit);
getch();
return 0;
}
]]>
Quote:
