Knapsack with sum of weights of about 10^9

Question

I encountered a problem in a programming competition a few weeks back, the problem was reducible to knapsack 0/1 problem.

But i couldn't do it because the maximum weight was about 10^9, so in c++ i couldn't use array. Although the number of items were about 10^5.

One way to solve this, that i could think of is using STL map, but not sure how to do this.

Any help would be appreciated. Thank You.

Answer 1

If all you need is a huge array, why don't you break it down to smaller ones?

class Huge_array{
    public:
    Huge_array(size_t max_size):
        max_size(max_size),
        store(max_size/v_size, vector<int>(v_size))
        {}

    int& operator[](size_t index)
    {  
        assert(0<=index && index<max_size); 
        return store[index/v_size][index%v_size]; 
    }

    private:
    size_t max_size;
    const int v_size=100000;
    vector<vector<int> > store;
};

I hope it does not have any typos.
Usage:

Huge_array my_array((size_t)10e9);
my_array[30000000]=10; // and so on upto size_t(10e9) - 1

If you need bigger values for value, you can make vector<int> to vector<long> or vector<double> or whatever in Huge_array.