c# - 0-1ナップサックアルゴリズム

Question

次の0-1ナップサック問題は解決可能ですか？

• 「float」の正の値と
• 「フロート」ウェイト（正または負の場合があります）
• ナップザックの「フロート」容量>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;
    }
}

Answer 2

ええ、力ずくで。これは NP 完全問題ですが、アイテムが 10 個未満になるため問題にはなりません。ブルートフォースは問題になりません。

        var size = 10;
        var capacity = 0;
        var permutations = 1024;
        var repeat = 10000;

        // Generate items
        float[] items = new float[size];
        float[] weights = new float[size];
        Random rand = new Random();
        for (int i = 0; i < size; i++)
        {
            items[i] = (float)rand.NextDouble();
            weights[i] = (float)rand.NextDouble();
            if (rand.Next(2) == 1)
            {
                weights[i] *= -1;
            }
        }

        // solution
        int bestPosition= -1;

        Stopwatch sw = new Stopwatch();            
        sw.Start();

        // for perf testing
        //for (int r = 0; r < repeat; r++)
        {
            var bestValue = 0d;

            // solve
            for (int i = 0; i < permutations; i++)
            {
                var total = 0d;
                var weight = 0d;
                for (int j = 0; j < size; j++)
                {
                    if (((i >> j) & 1) == 1)
                    {
                        total += items[j];
                        weight += weights[j];
                    }
                }

                if (weight <= capacity && total > bestValue)
                {
                    bestPosition = i;
                    bestValue = total;
                }
            }
        }
        sw.Stop();
        sw.Elapsed.ToString();