0-1背包算法

以下 0-1 背包问题是否可解：

• “浮动”正值和
• “浮动”权重（可以是正数或负数）
• 背包的“浮动”容量 > 0

我平均有

这是一个相对简单的二进制程序。

我建议用蛮力进行修剪。如果任何时候你超过了允许的重量，你不需要尝试其他物品的组合，你可以丢弃整棵树。

哦等等，你有negative重量？始终包括所有负权重，然后按照上述方法处理正权重。或者负重量的物品也有负价值吗？

包括所有具有正值的负重量项目。排除所有具有正重量和负价值的物品。

对于负值的负重量物品，减去其重量（增加背包容量）并使用代表的伪物品not拿走那个物品。伪物品将具有正的重量和价值。通过强力修剪来进行。

class Knapsack
{
    double bestValue;
    bool[] bestItems;
    double[] itemValues;
    double[] itemWeights;
    double weightLimit;

    void SolveRecursive( bool[] chosen, int depth, double currentWeight, double currentValue, double remainingValue )
    {
        if (currentWeight > weightLimit) return;
        if (currentValue + remainingValue < bestValue) return;
        if (depth == chosen.Length) {
            bestValue = currentValue;
            System.Array.Copy(chosen, bestItems, chosen.Length);
            return;
        }
        remainingValue -= itemValues[depth];
        chosen[depth] = false;
        SolveRecursive(chosen, depth+1, currentWeight, currentValue, remainingValue);
        chosen[depth] = true;
        currentWeight += itemWeights[depth];
        currentValue += itemValues[depth];
        SolveRecursive(chosen, depth+1, currentWeight, currentValue, remainingValue);
    }

    public bool[] Solve()
    {
        var chosen = new bool[itemWeights.Length];
        bestItems = new bool[itemWeights.Length];
        bestValue = 0.0;
        double totalValue = 0.0;
        foreach (var v in itemValues) totalValue += v;
        SolveRecursive(chosen, 0, 0.0, 0.0, totalValue);
        return bestItems;
    }
}