Распечатать значения решения для рюкзака

Question

У меня есть следующее решение проблемы с рюкзаком: (wt [] - массив весов, val [] - массив значений, n - размер массивов, индекс - текущий элемент, который мы пытаясь (для рекурсии) и обрами являются массивом, который представляет погоду или не пункт я был включен в растворе.

int knapSack(int W, int wt[], int val[], int n, int index, int arr[]) 
{ 
    if (n == index || W == 0) 
     return 0; 
    if (wt[index] > W) 
     return knapSack(W, wt, val, n, index+1); 

    int with=val[index]+knapSack(W-wt[index], wt, val, n, index+1); 
    int without=knapSack(W, wt, val, n, index+1); 

    if(with>without){ 
     arr[index]=1; 
     return with; 
    } 
    else{ 
     arr[index]=0; 
     return without; 
    } 

} 

Я пытаюсь напечатать, в этом рекурсивном решении элементов, которые выбраны, путем установки индексы взятых в массиве (res) до 1.
Как я понимаю, если with>without, это означает, что я выбираю текущий элемент или элемент #index. Так почему же это не возвращает правильное значение?
Я использую рекурсивный алгоритм по какой-либо причине, я знаю, что использование версии memoization может быть проще здесь. Пример:
Массы: 5 6 7 10 11
Значения: 2 4 5 6 9
W = 25
будет возвращать 5 из них в разрешении массива. Когда раствор равен 18 с пунктами 2,3,5 (начиная с индекса 1).

Answer 1

Предпосылка 1: в вашем коде, рекурсия вызовы knapSack не проходя arr, что должно привести к ошибке компиляции, я предполагаю, что это просто ошибка копирования/вставки.

Предпосылка 2: с данными вы предложили, в результате arr значение не все 1, как вы указали, но 01011, который до сих пор неправильно.

Рассмотрим гипотетическую ситуацию, в которой, во время выполнения вашей функции, with больше without: при расчете witharr заполняется соответствующими значениями; но затем запустите вычисление without, которое будет перезаписывать значения arr.

С with больше without, возвращенный arr будет неправильным, и это является причиной проблемы.

Простое исправление было бы сделать копию arr возвращенного with расчета, так что не собирается быть перезаписаны расчета without, например:

int with=val[index]+knapSack(W-wt[index], wt, val, n, index+1, arr); 

// copy the "with" arr 
int arrWith[n]; 
copyArr(arr, arrWith, n); 

int without=knapSack(W, wt, val, n, index+1, arr); 

if(with>without){ 
    // restore the "with" arr 
    copyArr(arrWith, arr, n); 

    arr[index]=1; 
    return with; 
} 
else{ 
    arr[index]=0; 
    return without; 
} 

copyArr просто:

void copyArr(int arr[], int arrDest[], int n) { 
    int i; 
    for(i = 0; i < n; i++) { 
     arrDest[i] = arr[i]; 
    } 
} 

С этим исправлением результирующее значение arr правильно 01101.