0-1背包算法

Question

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

• '浮动'正值和
• '浮动'权重(可以是正数或负数)
• 背包的"漂浮"能力> 0

我平均有10个项目,所以我正在考虑使用暴力实施.但是,我想知道是否有更好的方法.

Answer 1

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

我建议修剪蛮力.如果您在任何时候超过允许的重量,您不需要尝试其他项目的组合,您可以丢弃整个树.

哦,等一下,你有消极的权重？始终包括所有负权重,然后如上所述继续进行正权重.或负重量项也有负值？

包括具有正值的所有负重量项目.排除所有具有正重量和负值的项目.

对于具有负值的负重量项目,减去它们的重量(增加背包重量)并使用表示不接受该项目的伪项目.伪项将具有正重量和值.通过修剪蛮力进行.

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;
    }
}