0-1 Tam tersi yanlış yanıt veren sırt çantası (Dynamic Programming)

Question

Başlık oldukça açıklayıcı, birkaç gündür uğraşıyorum. Yanlış yaptığım aptal şey nedir? Sorun aynı ağırlıkta olan ve dolayısıyla değerler için bir girdi vektörüne sahip olmayan bir grup malzeme için, bu yüzden std :: max bölümünde bir değer eklememem olabilir, ama ben ' Bunu denedim ve doğru cevabı almamıştım. W, sırt çantası kapasitesidir, w, öğelerin ağırlıklarından oluşan bir vektördür.

#include <iostream> 
#include <vector> 

using std::vector; 
using std::max; 

int optimal_weight(int W, const vector<int> &w) { 
    size_t size = w.size(); 
    int knapsack[size+1][W+1]; 

    for (size_t a = 0; a <= size; a++) { 
     knapsack[a][0] = 0; 
    } 

    for (int b = 0; b <= W; b++) { 
     knapsack[0][b] = 0; 
    } 

    for (size_t i = 1; i <= size; i++) { 
      for (int j = 0; j <= W; j++) { 
        knapsack[i][j] = knapsack[i-1][j]; 

        if (w[i-1] <= j) { 
          knapsack[i][j] = std::max(knapsack[i-1][j-w[i-1]], knapsack[i-1][j]); 
        } 

       } 
     } 
     return knapsack[size][W]; 
    } 

Answer 1

kodunda hattı: int knapsack[size][W+1]

şekilde değiştirilmelidir: int knapsack[size+1][W+1]

Bu diziler 0 gelen endeksli ve 0 to size-1 için tanımlanan yukarıdaki durumda ve erişen edilir çünkü öğesinde index = size. Ayrıca, std::max hesaplanırken karşılık gelen ağırlıkları da ekleyin.