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

如果您需要更大的价值值，您可以vector<int>在.vector<long>vector<double>Huge_array