0-1 Knapsack algorithm

Question

Is the following 0-1 Knapsack problem solvable:

• 'float' positive values and
• 'float' weights (can be positive or negative)
• 'float' capacity of the knapsack > 0

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.

Solution 1

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.

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

Solution 2

Yeah, brute force it. This is an NP-Complete problem, but that shouldn't matter because you will have less than 10 items. Brute forcing won't be problematic.

        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();

Solution 3

If you can only have positive values then every item with a negative weight must go in.

Then I guess you could calculate Value/Weight Ratio, and brute force the remaining combinations based on that order, once you get one that fits you can skip the rest.

The problem may be that the grading and sorting is actually more expensive than just doing all the calculations.

There will obviously be a different breakeven point based on the size and distribution of the set.