ранец Алгоритм: Почему мы используем вес [я-1] вместо веса [I]

Question

Учитывая следующую часть реализации алгоритма ранца:

// Build table K[][] in bottom up manner 
for (i = 0; i <= n; i++) 
{ 
    for (w = 0; w <= W; w++) 
    { 
     if (i == 0 || w == 0) 
      K[i][w] = 0; 
     else if (wt[i - 1] <= w) 
      K[i][w] 
        = max(val[i - 1] + K[i - 1][w - wt[i - 1]], K[i - 1][w]); 
     else 
      K[i][w] = K[i - 1][w]; 
    } 
} 

У меня есть основные сомнения, почему мы используем вес [I -1], пока мы проверяем i-й элемент?

Answer 1

Ваш первый цикл для цикла i=0; i<=n; i++ означает, что он будет запускать n + 1 итераций, в то время как у вас есть только n объектов. Это нормально, потому что i = 0 имеет специальную оболочку для назначения K[i][w] = 0, поэтому в основном это инициализирует первую строку с 0s. Теперь, когда i = 0 имеет особое значение, массив смещается на 1 (так что i = 1 относится к первому объекту с весом wt [0] и т. Д.).

Вам не нужны такие трюки, но они распространены для динамического программирования. Если вы не хотите добавлять дополнительный столбец для 0, вы можете его опустить, но тогда вам нужно добавить кучу проверок, чтобы убедиться, что вы не пытаетесь получить доступ к памяти за пределами выделенной области, что делает ее немного сложнее проверить, так как у вас есть два пути для вашей логики.

Answer 2

Это дает нам лучшее значение, которое мы можем получить, если мы не выберем элемент i. Рассмотрите элементы (значение, объем); (2,1), (3,2), (4,5) и мешок объемом 5.

Когда мы имеем дело с третьим предметом, мы можем иметь значение 4. Но если мы не возьмем это, мы можем иметь наше предыдущее максимальное значение, которое равно 5. Check this video.