Yaklaşık 10^9

Question

ağırlıkları olan sırt çantasıyla bir kaç hafta önce bir programlama yarışmasında bir problemle karşılaştım, problem, 0/1 problemini çözebildi.

Ama bunu yapamam çünkü maksimum ağırlık yaklaşık 10^9'du, bu yüzden C++'da dizi kullanılamadım. Her ne kadar maddelerin sayısı yaklaşık 10^5 idi.

Bunu çözmenin bir yolu, düşünebildiğim STL haritasını kullanmaktır, ancak bunu nasıl yapacağınızdan emin değilim.

Herhangi bir yardım için teşekkür ederiz. Teşekkür ederim.

Answer 1

İhtiyacınız olan her şey çok büyük bir dizi ise, neden daha küçük olanlara ayırmıyorsunuz?

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

Umarız herhangi bir yazım hatası yoktur.
Kullanımı: Eğer değer için daha büyük değerler gerekiyorsa

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

, sen Huge_array içinde vector<int> ne olursa olsun vector<long> veya vector<double> veya yapabilirsiniz.