लगभग 10^9

Question

के वजन के साथ Knapsack कुछ हफ्ते पहले मुझे प्रोग्रामिंग प्रतियोगिता में कोई समस्या आई, समस्या 0/1 समस्या को कम करने के लिए कमजोर थी।

लेकिन मैं ऐसा नहीं कर सका क्योंकि अधिकतम वजन लगभग 10^9 था, इसलिए सी ++ में मैं सरणी का उपयोग नहीं कर सका। हालांकि वस्तुओं की संख्या लगभग 10^5 थी।

इसे हल करने का एक तरीका, मैं सोच सकता हूं कि एसटीएल मानचित्र का उपयोग कर रहा है, लेकिन यह सुनिश्चित नहीं है कि यह कैसे करें।

किसी भी मदद की सराहना की जाएगी। धन्यवाद।

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 

आप मूल्य के लिए बड़ा मूल्यों की आवश्यकता है, तो आप Huge_array में vector<int>vector<long> करने के लिए या vector<double> या जो कुछ भी कर सकते हैं।