c++ - 重量总和约为 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

如果你需要更大的值(value)，你可以制作vector<int>至 vector<long>或 vector<double>或 Huge_array 中的任何内容.