查找背包中的物品

我想用C#递归地解决背包问题。这是我的代码：

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是项目的数量，remain是最大重量。

我的问题是check大批。我已经使用这个数组来存储将要放入包中的物品，但它并不总是有效，有时解决方案是正确的，有时则不是。我已经尝试了一切，但无法弄清楚。我该如何解决这个问题？

检查数组的使用是错误的，因为它指示最后一次分配，并且不一定是所选的分配。

这是一个反例，解释了为什么它不起作用。

Assume:

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

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

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（选择第二个元素），但您的解决方案不选择任何元素（check = [0,0]）

发生这种情况是因为check是全局的，而不是调用环境本地的，特别是 - 深层的分配不取决于您在更高级别中所做的选择。

要处理它，您可以：

1. 使您的列表不是全局的，并且每个递归调用都会有自己的 列表的实例。 “parent”调用不仅会选择哪个 值得采取，但根据这个选择 - 父母也会 选择它将使用的列表，并将“他的”选择附加到它，然后转发到其父级。
2. 切换到DP解决方案 http://en.wikipedia.org/wiki/Knapsack_problem#0.2F1_knapsack_problem，或模仿 DP 解决方案，然后使用您创建的表来确定要选择哪些元素，如我在此线程中所述：如何使用背包算法找到袋子里有哪些元素[而不仅仅是袋子的价值]？ https://stackoverflow.com/a/7489482/572670