The revolutionary project management tool is here! Plan visually with a single glance and make sure your projects get done.
// Required C++ libraries and header files
#include <iostream>
#include <iomanip>
#include <fstream>
#include <cstdlib>
#include <math.h>
#include <limits.h>
using namespace std;
#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 optimal 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()
{
int profit, no, cap;
knapsack k;
k.getdetails(no, cap);
k.initialise();
profit = k.mfknapsack(no, cap);
k.display(profit);
system("pause");
return 0;
}
DataEntry-2-Sets.xls
for (i = 1; i <= n; i++)
{
cout << endl;
cout << "Weight[" << i << "] = ";
cin >> obj[i-1].weight;
cout << "Value[" << i << "] = ";
cin >> obj[i-1].value;
}
cout << "debugging n = " << n;
if (c < obj[n].weight)
...
I worry about lines 65 and 69 in particular. The first time that mfknapsack is called, is "n" equal to 10 or 9? If 10, then you have a problem using obj[n] in those places.
profit = k.mfknapsack(no-1, cap);
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;
}
}
profit = k.mfknapsack(no-1, cap);
Error-withLargeNumbers.jpg
profit = k.mfknapsack(no-1, cap-1);
// Required C++ libraries and header files
#include <iostream>
#include <iomanip>
#include <fstream>
#include <cstdlib>
#include <math.h>
#include <limits.h>
using namespace std;
#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 optimal 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()
{
int profit, no, cap;
knapsack k;
k.getdetails(no, cap);
k.initialise();
profit = k.mfknapsack(no, cap);
//profit = k.mfknapsack(no-1, cap-1); // commented out
k.display(profit);
system("pause");
return 0;
}
OutputWithSmallValues.jpg 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;
}
// Required C++ libraries and header files
#include <iostream>
#include <iomanip>
#include <fstream>
#include <cstdlib>
#include <math.h>
#include <limits.h>
using namespace std;
#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-1].weight;
cout << "Value[" << i << "] = ";
>>>>> cin >> obj[i-1].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 count, int cap)
{
int val, temp, temp1;
>>>>> int n = count - 1;
>>>>> int c = cap - 1;
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 optimal subset are: ";
>>>>> I can't figure out what you are trying to do exactly, but I know that this won't work the way you have it.
>>>>> next = n - 1;
>>>>> cap = capacity - 1;
>>>>> 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()
{
int profit, no, cap;
knapsack k;
k.getdetails(no, cap);
k.initialise();
profit = k.mfknapsack(no, cap);
//profit = k.mfknapsack(no-1, cap-1); // commented out
k.display(profit);
system("pause");
return 0;
}
#define MAX_N 10
#define MAX_CAP 50
class knapsack
{
private : int n, capacity, value[MAX_N][MAX_CAP];
...
// Required C++ libraries and header files
#include <iostream>
#include <iomanip>
#include <fstream>
#include <cstdlib>
#include <math.h>
#include <limits.h>
using namespace std;
#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-1].weight; // sjklein42's recommendation
cout << "Value[" << i << "] = ";
cin >> obj[i-1].value; // sjklein42's recommendation
}
}
void knapsack :: initialise()
{
int i, j;
for (i = 0; i < n; i++) // sjklein42's recommendation
for (j = 0; j < capacity; j++) // sjklein42's recommendation
{
if (i == 0 || j == 0)
value[i][j] = 0;
else
value[i][j] = -1;
}
}
int knapsack :: mfknapsack(int count, int cap) // sjklein42's recommendation
{
int val, temp, temp1;
int n = count - 1; // sjklein42's recommendation
int c = cap - 1; // sjklein42's recommendation
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 optimal subset are: ";
// I can't figure out what you are trying to do exactly, but I know that this won't work the way you have it. // sjklein42's comment
// next = n - 1; // sjklein42's recommendation
//cap = capacity - 1; // sjklein42's recommendation
//
//for (i = n; i > 0; i--) // sjklein42's recommendation
//{
// if (value[next][cap] != value[next - 1][cap]) // sjklein42's recommendation
// {
// cout << i << " ";
// cap -= obj[i].weight;
// }
// next = i - 1;
//}
// sjklein42's recommendation (full replacement of next 11 lines -- change from above)
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()
{
int profit, no, cap;
knapsack k;
k.getdetails(no, cap);
k.initialise();
profit = k.mfknapsack(no, cap);
//profit = k.mfknapsack(no-1, cap-1); // EEH's comment
k.display(profit);
system("pause");
return 0;
}
// Required C++ libraries and header files
#include <iostream>
#include <iomanip>
#include <fstream>
#include <cstdlib>
#include <math.h>
#include <limits.h>
using namespace std;
// #define MAX 10 // Replaced per sjklein42's recommendation
#define MAX_N 10 // sjklein42's recommendation
#define MAX_CAP 50 // sjklein42's recommendation
class knapsack
{
//private : int n, capacity, value[MAX][MAX];
private : int n, capacity, value[MAX_N][MAX_CAP];
struct object
{
int weight;
int value;
//} obj[MAX]; // Replaced per sjklein42's recommendation
} obj[MAX_N]; // sjklein42's recommendation
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-1].weight; // sjklein42's recommendation
cout << "Value[" << i << "] = ";
cin >> obj[i-1].value; // sjklein42's recommendation
}
}
void knapsack :: initialise()
{
int i, j;
for (i = 0; i < n; i++) // sjklein42's recommendation
for (j = 0; j < capacity; j++) // sjklein42's recommendation
{
if (i == 0 || j == 0)
value[i][j] = 0;
else
value[i][j] = -1;
}
}
int knapsack :: mfknapsack(int count, int cap) // sjklein42's recommendation
{
int val, temp, temp1;
int n = count - 1; // sjklein42's recommendation
int c = cap - 1; // sjklein42's recommendation
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 optimal subset are: ";
// I can't figure out what you are trying to do exactly, but I know that this won't work the way you have it. // sjklein42's comment
// next = n - 1; // sjklein42's recommendation
//cap = capacity - 1; // sjklein42's recommendation
//
//for (i = n; i > 0; i--) // sjklein42's recommendation
//{
// if (value[next][cap] != value[next - 1][cap]) // sjklein42's recommendation
// {
// cout << i << " ";
// cap -= obj[i].weight;
// }
// next = i - 1;
//}
// sjklein42's recommendation (full replacement of next 11 lines -- change from above)
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()
{
int profit, no, cap;
knapsack k;
k.getdetails(no, cap);
k.initialise();
profit = k.mfknapsack(no, cap);
//profit = k.mfknapsack(no-1, cap-1); // EEH's comment
k.display(profit);
system("pause");
return 0;
}
MaxCap.jpg// Required C++ libraries and header files
#include <iostream>
#include <iomanip>
#include <fstream>
#include <cstdlib>
#include <math.h>
#include <limits.h>
using namespace std;
#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 = 0; i < n; i++) // Sara's recommendation... change from: 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 < MAX; i++) // Sara's recommendation... change from: for (i = 0; i <= n; i++)
for (j = 0; j < MAX; j++) // Sara's recommendation... change from: for (j = 0; j <= capacity; j++)
{
if (i == 0 || j == 0)
value[i][j] = 0;
else
value[i][j] = -1;
}
}
int knapsack :: mfknapsack(int r, int c) // Sara's recommendation... change from: int knapsack :: mfknapsack(int n, int c)
{
int val, temp, temp1;
if (value[r][c] < 0) // Sara's recommendation... change from: if (value[n][c] < 0)
{
temp = mfknapsack(r - 1, c); // Sara's recommendation... change from: if (c < obj[n].weight)
if (c < obj[r].weight) // Sara's recommendation... change from: if (c < obj[n].weight)
val = temp;
else
{
temp1 = obj[r].value + mfknapsack(r - 1, c - obj[r].weight); // Sara's recommendation... change from: temp1 = obj[n].value + mfknapsack(n - 1, c - obj[n].weight);
if (temp1 > temp)
val = temp1;
else
val = temp;
}
value[r][c] = val; // Sara's recommendation... change from: value[n][c] = val;
}
return (value[r][c]); // Sara's recommendation... change from: return (value[n][c]);
}
void knapsack :: display(int cost)
{
int i, next, cap;
cout << "\nThe objects included in the optimal subset are: ";
next = n-1; // Sara's recommendation... change from: next = n;
cap = capacity-1; // Sara's recommendation... change from: cap = capacity;
for (i = n-1; i > 0; i--) // Sara's recommendation... change from: cap = capacity;
{
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()
{
int profit, no, cap;
knapsack k;
k.getdetails(no, cap);
k.initialise();
profit = k.mfknapsack(no, cap);
k.display(profit);
system("pause");
return 0;
}
Answer----Incorrect-1.jpgvoid knapsack :: display(int cost)
{
int i, next, cap;
cout << "\nThe objects included in the optimal 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;
}
Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.
Have a better answer? Share it in a comment.
Line 36 is the problem: for (i = 1; i <= n; i++)
Unlike BASIC, array indices start at zero in C.
You should review the rest of your code to make sure this is the paradigm you are using.