我想递归地解决背包问题在C＃。这是我的code：

I want to solve the knapsack problem recursively in C#. This is my code:

public  int f(int n, int remain)
{
    if (n < 0) return 0;
    if (w[n] > remain)
    {
        //    Thread.VolatileWrite(ref   check[n], 0);
        check[n] = 0;
        return f(n - 1, remain);
    }
    else
    {
        int a = f(n - 1, remain);
        int b = p[n] + f(n - 1, remain - w[n]);
        if (a >= b)
        {
            //   Thread.VolatileWrite(ref   check[n], 0);
            check[n] = 0;
            return a;
        }
        else
        {
            //  Thread.VolatileWrite(ref   check[n], 1);
            check[n] = 1;
            return b;
        }
    }
}

是W 是保存重量和 P 是包含价格的数组的数组。 N 是项目的数量和继续的最大重量。

w is an array that holds weights and p is an array that holds prices. n is the number of items and remain is the maximum weight.

我的问题是与检查阵列。本人已经用这种阵列来存储将要在袋内物品，但它并不总是工作，有时溶液是正确的，有时没有。我曾尝试一切，但不能看着办吧。我该如何解决这个问题？

My problem is with the check array. I have used this array to store items that are going to be in the bag but it does not work always, sometimes the solution is right and sometimes not. I have tried everything but could not figure it out. How can I solve this?

推荐答案

校验阵列的用法是错误的，因为它表示最后的分配，并且它不具有要在一个所选择

The usage of the check array is wrong, since it indicates the last assignment, and it does not have to be the one chosen.

下面是解释了为什么这是行不通的一个反例。

Here is a counter example that explains why it does not work.

假设：

weights = [1,2]
values = [2,1]
w = 2

现在，让我们检查会发生什么：

Now, let examine what will happen:

f(1,2):
   f(0,2):
       f(-1,2)  = 0
       a = 0
       f(-1,1) = 0
       b = 2 + 0 = 2
       b>a -> check[0] = 1
    return f(0,2) = 2
    a = 2
    f(0,0):
       w[0] > 0: check[0] = 0
       return f(-1,0) = 0
    return f(0,0) = 0
    b = 1 + 0 = 1
    a > b: check[1] = 0
return  f(1,2) = 2

所以，这个问题的最优解是2（艇员选拔第二个元素），但您的解决方案选择没有元素（查= [0,0]）

So, the optimal solution to this problem is 2 (chosing the 2nd element), but your solution chose no element (check = [0,0])

这是因为的变化检查是全球性的，而不是本地的调用环境，特别 - 分配的深层次不依赖于你所做的选择在较高的水平。

This happens because the changing of check is global, and not local to the calling environment, and specifically - the assignment in deep levels do not depend on the choice you made in higher levels.

要处理它，您可以：

请您的清单没有全球性的，每次递归调用都会有自己的 比如清单。 父通话不仅会选择哪 值取，但根据这个选择 - 父还将 选择它将使用，并追加他的选择，它的列表中，转发至其父前。 切换到 DP解决方案或模仿DP解决方案，然后使用该表创建以想出选择，因为我在这个线程中描述的元素：如何找到哪些元素是囊中，用背包算法[不仅包包的价值] make your list not global, and each recursive call will have its own instance of a list. The "parent" call will chose not only which value to take, but according to this choice - the parent will also chose the list it will use, and append "his" choice to it, before forwarding up to its parent. Switch to a DP solution, or mimic the DP solution, and then use the table you created to figure out which elements to chose as I described in this thread: How to find which elements are in the bag, using Knapsack Algorithm [and not only the bag's value]?