ダイナミックプログラミングを使用したナップザック

Question

ダイナミックプログラミングを使用してナップザック問題を解決するための共通のアルゴリズムがあります。しかし、W = 750000000では正しく動作しません。なぜなら、不正なallocのエラーがあるからです。どのようにWの私の価値のためにこの問題を解決するための任意のアイデア？

int n=this->items.size(); 
std::vector<std::vector<uint64_t>> dps(this->W + 1, std::vector<uint64_t>(n + 1, 0)); 
for (int j = 1; j <= n; j++) 
    for (int k = 1; k <= this->W; k++) { 
     if (this->items[j - 1]->wts <= k) 
      dps[k][j] = std::max(dps[k][j - 1], dps[k - this->items[j - 1]->wts][j - 1] + this->items[j - 1]->cost); 
     else 
      dps[k][j] = dps[k][j - 1]; 
    } 

Answer 1

まず、ナップザック問題を解決するために1つのディメンションのみを使用できます。これはあなたのメモリをdp [W] [n]（n * W空間）からdp [W]（W空間）に減らします。ここで見ることができます：0/1 Knapsack Dynamic Programming Optimazion, from 2D matrix to 1D matrix

しかし、あなたがdp [W]だけを使用しても、あなたのWは本当に高く、メモリが多すぎるかもしれません。あなたのアイテムが大きい場合、可能な重みの数を減らすためにいくつかのアプローチを使用することができます。まず、Wのすべての位置が必要ではなく、体重の合計[i]が存在するようなものだけが必要であることを認識してください。例えば

：アイテムは位置のみp = [0, 100, 200, 300, 400, 500]を占めることができるので、

W = 500 
weights = [100, 200, 400] 

あなたは、あなたのマトリックスの位置DP [473]を使用することはありません。

W = 5 
weights = [1,2,4] 

別のより複雑な例：：この問題はときと同じであることを確認することは容易である前と同じアプローチを使用して

W = 20 
weights = [5, 7, 8] 

、あなたは0からすべての重みを必要としません20、アイテムが位置のみ

p = [0, 5, 7, 5 + 7, 5 + 8, 7 + 8, 5 + 7 + 8] 
p = [0, 5, 7, 12, 13, 15, 20] 

にいっぱいに占有することができる、とあなたは[Pの大きさを] DPするDPから[20]を、あなたの行列を減らすことができますので、= M [7]。

Answer 2

あなたはnを示しているが、我々はそれが1であると仮定した場合でも、あなたが割り当てしようとしているどのくらいのデータを確認することができますしません。だから、それは次のようになります。私は、これはあなたのプログラムができるようになりますその後、より多くのスペースで推測してい

750000000*64*2 bits = ~11.1758Gb 

：

W*64*2 // Here we don't consider overhead of the vector 

これがあることを出てきます。あなたは新しいアプローチをとる必要があるでしょう。おそらく、複数のブロックとして問題を処理しようとします。最初と後半のセパラトリーを考えて、交換してください。