c++ - 重さの合計が約 10^9 のナップザック

Question

数週間前のプログラミング コンテストで問題に遭遇しました。この問題はナップザック 0/1 問題に還元できました。

しかし、最大の重みが約10 ^ 9だったのでできませんでした。そのため、C ++では配列を使用できませんでした。アイテム数は約10^5でしたが。

これを解決する1つの方法は、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。