matrix not updating in knapsack algorithm

18 Views Asked by At

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

0

There are 0 best solutions below