C++ ‘std::out_of_range’ error from 0-1 Knapsack code

  c++, recursion, vector

I am currently working on a program to solve the 0-1 Knapsack problem using vectors, not arrays.

First it reads from a file called "knapsack1", for example,

10
2 10
4 6
6 4
8 2
1 20
3 17

where the number on top is the capacity, 1st column is the items’ weight, 2nd column is the item’s worth.

The program divides the 2 columns into 2 vectors then calculates the maximum value.

My current code is:

#include <iostream>
#include <fstream>
#include <vector>
#include <string>

int max(int a, int b) { return (a > b) ? a : b; }

int calculateKnapsack(std::vector<int> weight, std::vector<int> worth, int capacity, int n)
{
    int itemWorth, itemWeight;

    if (weight.at(n - 1) > capacity)
    {
        weight.pop_back();
        worth.pop_back();
        n--;

        return calculateKnapsack(weight, worth, capacity, n);
    }
 
    else
    {
        itemWeight = weight.at(n - 1);
        itemWorth = worth.at(n - 1);
        
        weight.pop_back();
        worth.pop_back();
        n--;

        return max((itemWorth + calculateKnapsack(weight, worth, capacity - itemWeight, n)), calculateKnapsack(weight, worth, capacity, n));
    }
}

void divide(std::vector<int> &data, std::vector<int> &weight, std::vector<int> &worth)
{
    unsigned int i;
    for (i = 1; i < data.size(); i++)
    {
        if (i % 2 == 0)
        {
            worth.push_back(data.at(i));
        }
        else
        {
            weight.push_back(data.at(i));
        }
    }
}


int main()
{
    std::ifstream inputFile("knapsack1");

    std::vector<int> data;
    int numbers;

    while (inputFile >> numbers)
    {
        data.push_back(numbers);
    }

    int capacity = data.at(0);
    std::vector<int> weight;
    std::vector<int> worth;

    divide(data, weight, worth);

    int n = worth.size();

    calculateKnapsack(weight, worth, capacity, n);

    std::cout << calculateKnapsack(weight, worth, capacity, n);
}

However it throws ‘std::out_of_range’ every time I try to run, and I can’t figure out why. I’ve noticed that the divide function works fine.

If you’re able to determine what the error is would you please let me know? Thank you!

Source: Windows Questions C++

LEAVE A COMMENT