0-1 Целочисленный рюкзак, возвращающий неверный ответ (динамическое программирование)

Question

Название довольно понятно, я уже пару дней перебирал его. Какая глупость, что я делаю неправильно? Проблема заключается в связке материалов, которые имеют одинаковую массу и, следовательно, не имеют входного вектора для значений, поэтому может быть фактом, что я не добавляю значение в std :: max part, вы пытались это сделать и не получили правильного ответа. W - емкость рюкзака, w - вектор, состоящий из весов предметов.

#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

Строка в коде: int knapsack[size][W+1]

должен быть изменен на: int knapsack[size+1][W+1]

Это происходит потому, что массивы индексируются 0 и в предыдущем случае, определенной для 0 to size-1 и вы получаете доступ к элемент на index = size. Также добавьте соответствующие веса при расчете std::max.