0-1背包算法 [英] 0-1 Knapsack algorithm

问题描述

在下面的0-1背包问题可解的：

Is the following 0-1 Knapsack problem solvable:

• 在浮动正面的价值观和
• 浮动的权重（可以是正或负）
• 背包> 0

我对平均＆LT; 10个项目，所以我想用蛮力实施。不过，我想知道是否有这样做的更好的方法。

I have on average < 10 items, so I'm thinking of using a brute force implementation. However, I was wondering if there is a better way of doing it.

推荐答案

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

This is a relatively simple binary program.

我建议蛮力与修剪。如果您在任何时候超过允许的体重，你不必尝试其他项目的组合，你可以放弃整个树。

I'd suggest brute force with pruning. If at any time you exceed the allowable weight, you don't need to try combinations of additional items, you can discard the whole tree.

哦，等一下，你有否定的权重？包括所有负权重始终，然后按照上面的积极的权重。还是做负重量的物品也有负值？

Oh wait, you have negative weights? Include all negative weights always, then proceed as above for the positive weights. Or do the negative weight items also have negative value?

包括所有的负重量的物品有正面价值。排除与积极的重量和负值的所有项目。

Include all negative weight items with positive value. Exclude all items with positive weight and negative value.

有关负重量的物品与负值，减去的体重（增加背包capavity），并使用一个伪项目从而重新presents的没有的考虑该项目。伪项目将具有正的重量和价值。蛮力删减继续。

For negative weight items with negative value, subtract their weight (increasing the knapsack capavity) and use a pseudo-item which represents not taking that item. The pseudo-item will have positive weight and value. Proceed by brute force with pruning.

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

这篇关于0-1背包算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！