0

我有一个代码，它给出了通过用最佳重量组填充背包可以获得的最大值。

int arr[5] = {0, 0, 0, 0, 0};
int Weight[5] = {2, 5, 8, 7, 9};
int Value[5]  = {4, 5, 7, 9, 8};
const int n = 5;
const int maxCapacity = 20;

int maximum(int a, int b)
{
    return a > b ? a : b;
}

int knapsack(int capacity, int i)
{
    if (i > n-1) return 0;

    if (capacity < Weight[i])
    {
        return knapsack(capacity, i+1);
    }
    else
    {
        return maximum (knapsack(capacity, i+1),
                        knapsack(capacity - Weight[i], i+1) + Value[i]);
    }
}

int main (void)
{
    cout<<knapsack(maxCapacity,0)<<endl;
    return 0;
}

我需要通过打印所有权重用于找到最佳解决方案来扩展此解决方案。为此，我计划使用一个初始化为 0 的数组 arr。每当使用权重时，我将 arr 中的相应位置标记为 1，否则它保持为 0。

我想到的第一件事是更改 maximum() 函数，如下所示

int maximum(int a, int b, int i)
{
    if (a > b)
    {
        if (arr[i] == 1) arr[i] = 0;
        return a;
    }
    else
    {
        if (arr[i] == 0) arr[i] = 1;
        return b;
    }
}

但即使是这种解决方案也因权重和值的某些组合而失败。关于如何前进的任何建议？

4

1 回答 1

0

The problem is that you dont know which one of the two options are selected by this command

return maximum (knapsack(capacity, i+1),
                knapsack(capacity - Weight[i], i+1) + Value[i]);

I guess you can use two variables to store the values and if the weight is selected( the value of that variable is bigger ) you can add it to the array . Hope that solves your problem.

于 2012-10-29T07:11:42.543 回答