for some reason, my program returns: answer 0, used weight is negative, indices are only 0. i couldnt resolve the issue.
#define INF 10000000
#define MIN -10000000
using namespace std;
vector<int> indices;
struct Item {
int value;
int weight;
};
int knapsack(vector<Item>& items, int W, int v_max){
int n = items.size();
// int v_max = MIN;
// for (int i = 0; i < n; i++) {
// v_max = max(v_max, items[i].value);
// }
int V = n * v_max;
vector<vector<int>> OPT(n + 1, vector<int>(V + 1, INF));
for(int i = 0; i <= n; i++){
for(int v = 0; v <= V; v++){
if(v ==0) OPT[i][v] = 0;
else if(i == 0 && v > 0) OPT[i][v] = INF;
else if(items[i - 1].value <= v){
OPT[i][v] = min(OPT[i - 1][v], items[i].weight + OPT[i - 1][v - items[i - 1].value]);
}
else{
OPT[i][v] = OPT[i - 1][v];
}
}
}
int max_value = 0;
for(int v = 0; v <= V; v++){
if(OPT[n][v] <= W){
max_value = v;
}
else{
break;
}
}
//clear index vector
indices.clear();
//resize index vector
indices.resize(n+1);
int v = max_value;
for(int i = n; i > 0; i--){
if(OPT[i][v] != OPT[i - 1][v]){
indices.push_back(i);
v = v - items[i - 1].value;
}
}
cout << endl << endl;
return max_value;
}
int main(){
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
int n, W;
cin >> n >> W;
vector<Item> items(n);
for(int i = 0; i < n; i++){
cin >> items[i].value >> items[i].weight;
}
//determine the maximum value
int v_max = MIN;
for(int i = 0; i < n; i++){
v_max = max(v_max, items[i].value);
}
int org_ans = knapsack(items, W, v_max);
cout << "Original Instance:" << endl;
cout << "Answer: " << org_ans << endl;
int used_weight = 0;
for(int i = 0; i < indices.size(); i++){
used_weight += items[indices[i] - 1].weight;
}
cout << "Used Weight: " << used_weight << endl;
cout << "Indices: ";
for(int i = 0; i < indices.size(); i++){
cout << indices[i] << " ";
}
cout << endl << endl;
}
i printed some lines between my loops nd functions. looks like it is going through the loop properly, but it isnt updating the matrix. how can i debug this?
output for this: Original Instance: Answer: 0 Used weight: 0 indices: 0 0 0 0 0 0 ......... (goes on)
TIA