打印背包解决方案的值

-1

我对背包问题有以下解决方案：（wt []是权重数组，val []是值数组，n是数组大小，index是当前项目，我们是尝试（用于递归）和改编是表示天气或不项目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。那么为什么这不会返回正确的值？
我使用递归算法的原因，我知道使用memoization版本可以在这里更容易。实施例：
重量：5个6 7 10 11
值：2 4 5 6 9
W = 25
将返回5对那些在阵列水库当项目2,3,5的解决方案为18时（从索引1开始）。

来源

2016-12-28 Yinon Eliraz

为什么添加赏金？我想投票支持，因为没有[MCVE]（http://stackoverflow.com/help/mcve）。 – melpomene

添加了一个示例。 –

代码的其余部分在哪里？ – melpomene

前提1：在你的代码，递归调用knapSack没有经过arr，这应该引起编译错误，我认为它只是一个复制/粘贴错误。

前提2：你提出的数据，所产生的arr值是不是所有1如你所指出的，但是01011，这仍然是不正确。

考虑你的函数的执行过程中的假设情况，with比without更大：在with计算期间arr充满了正确的价值观;但是然后开始计算without，这将会覆盖arr值。

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

一个简单的解决方法是使由with计算所以它是不会被without计算覆盖返回arr的副本，例如：

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。

来源

2017-01-01 19:22:30

打印背包解决方案的值

回答

相关问题