Получение списка выбранных элементов в матрице DP Knapsack

Question

Я попытался реализовать стек Overflow Answered Solution. Но это не работает.

Контрольный пример:

int val[] = {10,40,30,50}; 
    int wt[] = {5,4,6,3}; 
    W = 10; 

ВЫХОД Ранцевые DP-МАТРИЦА:

0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 5 5 5 5 5 5 
0 0 0 0 4 5 5 5 5 9 9 
0 0 0 0 4 5 6 6 6 9 10 
0 0 0 3 4 5 6 7 8 9 10 

вес, который может быть достигнут в: 10

сумма масс выбранных элементов : 11 (что является Онг должен быть только 10)

выбрано -> 6 (третий пункт) и 5 ​​(первый пункт) [который является неправильным]

int knapSack(int W, int wt[], int val[], int n) 
{ 
int i, w; 
int K[n+1][W+1]; 
    int picks[n+1][W+1] = {0}; 
    // 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){ 
      //val[i-1 ] is value of curr i 
      K[i][w] = max(wt[i-1] + K[i-1][w-wt[i-1]], K[i-1][w]); 
      if (val[i-1]+K[i-1][w-wt[i-1]] > K[i-1][w]){ 
       picks[i][w]=1; 
      } 
      else 
       picks[i][w]=-1; 
     } 
     else{ 
     // wt of individual is > limit 
      picks[i][w] = -1; 
      K[i][w] = K[i-1][w]; 
    } 
    } 
    } 
} 

Для печати отборных элементов, я использую

while (w > 0 && i > 0){ 

if ((K[i][w] - K[i-1][w-wt[i-1]]) == wt[i-1]){ 
    weight += wt[i-1]; 
    i = i - 1; 
    w = w - wt[i-1]; 
} 
else{ 
    i = i - 1; 
} 

} 

Answer 1

w = w - wt[i-1] 

фактически

w = w - wt[i-2] 

поскольку i = i - 1 вычисляется перед ним. Ниже код будет работать сейчас.

weight += wt[i-1]; 
    i = i - 1; 
    w = w - wt[i] ;