Как найти предметы в оптимальном решении задачи о ранце с помощью динамического программирования?

Question

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

#include<stdio.h>

int getMax(int x, int y) {
    if(x > y) {
        return x;
    } else {
        return y;
    }
}

int main(void) {

    //the first element is set to -1 as
    //we are storing item from index 1
    //in val[] and wt[] array
    int val[] = {-1, 100, 20, 60, 40};  
    int wt[] = {-1, 3, 2, 4, 1};   
    int A[] = {0,0,0,0,0};    
    int n = 4; //num
    int W = 5;//cap  
    int i, j;


    // value table having n+1 rows and W+1 columns
    int V[n+1][W+1];

    // fill the row i=0 with value 0
    for(j = 0; j <= W; j++) {
        V[0][j] = 0;
    }

    // fill the column w=0 with value 0
    for(i = 0; i <= n; i++) {
        V[i][0] = 0;
    }

    //fill the value table
    for(i = 1; i <= n; i++) {
        for(j = 1; j <= W; j++) {
            if(wt[i] <= j) {
                V[i][j] = getMax(V[i-1][j], val[i] + V[i-1][j - wt[i]]);
            } else {
                V[i][j] = V[i-1][j];
            }
        }
    }

    //max value that can be put inside the knapsack
    printf("Max Value: %d\n", V[n][W]);


    //==================================find items
    int n1,c;
    n1=n;
    c=W;
    int A2[n1][c];

    while(c>0){

        if(A2[n1][c]==A2[n1-1][c]){
            A[n1]=0;
        } else {
            A[n1]=1;
        }

        n1=n1-1;
        c=c-wt[n1];

    }

    printf("Final array of items: ");
    for(i = 0; i < n; i++){
        printf("%d",A[i]);
    }
} // end of main

И этовывод:

Max Value: 140
Final array of items: 0001

Предполагается, что эта строка единиц и нулей является окончательно выбранными элементами, но из решения это кажется неправильным!

Я следовал этому алгоритму:

While the remaining capacity is greater than 0 do
If Table[n, c] = Table[n-1, c] then
Item n has not been included in the optimal solution
Else
Item n has been included in the optimal solution
Process Item n
Move one row up to n-1
Move to column c – weight(n)

Итак, этот алгоритм неверен / не подходит для этого метода, или я что-то упустил?