Являются ли эти 2 алгоритма ранца одинаковыми?(Они всегда выводят одно и то же)

Question

В моем коде предполагается, что C - это емкость, N - это количество предметов, w [j] - вес предмета j, а v [j] - это стоимость предмета j, делает ли он то же самое, что иалгоритм ранца 0-1?Я пробовал свой код на некоторых наборах данных, и, похоже, это так.Мне интересно это потому, что алгоритм ранца 0-1, который мы изучали, является двумерным, тогда как он одномерный:

for (int j = 0; j < N; j++) {
    if (C-w[j] < 0) continue;
    for (int i = C-w[j]; i >= 0; --i) { //loop backwards to prevent double counting
        dp[i + w[j]] = max(dp[i + w[j]], dp[i] + v[j]); //looping fwd is for the unbounded problem
    }
}
printf( "max value without double counting (loop backwards) %d\n", dp[C]);

Вот моя реализация 0-1алгоритм ранца: (с одинаковыми переменными)

for (int i = 0; i < N; i++) {
    for (int j = 0; j <= C; j++) {
        if (j - w[i] < 0) dp2[i][j] = i==0?0:dp2[i-1][j];
        else dp2[i][j] = max(i==0?0:dp2[i-1][j], dp2[i-1][j-w[i]] + v[i]);
    }
}
printf("0-1 knapsack: %d\n", dp2[N-1][C]);

Answer 1

Да, ваш алгоритм дает вам тот же результат.Это усовершенствование классического ранца 0-1 достаточно популярно: Википедия объясняет это следующим образом:

Кроме того, если мы используем только одномерный массив m [w] длясохраняем текущие оптимальные значения и передаем этот массив i + 1 раз, каждый раз переписывая с m [W] на m [1], мы получаем тот же результат только для пространства O (W).

Обратите внимание, что они конкретно упоминают вашу обратную петлю.