打印背包解决方案的值

Question

对于背包问题，我有以下解决方案：（wt[] 是权重数组，val[] 是值数组，n 是数组大小，index 是我们正在尝试的当前项目（对于递归）和 arr 是一个数组，表示天气或不是项目 i 是否包含在解决方案中。

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。那么，为什么这不是 return 正确的值？
我使用递归算法是有原因的，我知道在这里使用记忆版本会更容易。示例：
权重：5 6 7 10 11
值：2 4 5 6 9
W=25
将 return 数组 res 中的 5 个。当解决方案为 18 且项目为 2、3、5（从索引 1 开始）时。

Answer 1

前提 1：在您的代码中，对 knapSack 的递归调用未通过 arr，这应该会导致编译错误，我认为是只是一个 copy/paste 错误。

前提 2：根据您提出的数据，得到的 arr 值并不像您指出的那样全部 1，而是 01011 , 这仍然是不正确的。

考虑假设情况，在您的函数执行期间，with 大于 without：在 with 计算期间，arr 填充了正确的价值观；但随后开始 without 计算，它将覆盖 arr 值。

由于with大于without，返回的arr会是错误的，这就是问题的原因。

一个简单的修复方法是复制 with 计算返回的 arr，这样它就不会被 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。

打印背包解决方案的值

Print the values of knapsack solution

c

recursion

knapsack-problem