背包总重量约为10 ^ 9

Question

我在几周前的编程竞赛中遇到了一个问题,问题是可以减少到背包0/1的问题.

但我不能这样做,因为最大重量大约是10 ^ 9,所以在c ++我不能使用数组.虽然物品数量约为10 ^ 5.

解决这个问题的一种方法,我能想到的是使用STL地图,但不知道如何做到这一点.

任何帮助,将不胜感激.谢谢.

Answer 1

如果您需要的只是一个巨大的数组，为什么不将其分解为较小的数组呢？

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;
};

我希望它没有任何错别字。
用法：

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

如果您需要更大的价值，您可以vector<int>在vector<long>或vector<double>中进行任何操作Huge_array。