Software Programming

Kunuk Nykjaer

0-1 Knapsack brute force and pruning with C#

with one comment


Knapsack

knapsack

Here I test a brute force and pruning implementation to solve 0-1 Knapsack problem.
Because Knapsack is NP for floating numbers the algorithms will only be usable for few items.

Brute Force

This is an implementation where negative values and weights of floating numbers are allowed.

This is only usable if the items list is small (max ~20 items).
A better approach is to use pruning technique if more items are needed.

program.cs

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Globalization;
using System.Threading;

/// <summary>
/// Author: Kunuk Nykjaer
/// 0-1 Knapsack brute force
/// code adapted from
/// http://stackoverflow.com/questions/8125309/0-1-knapsack-algorithm
/// </summary>
public class Program
{
    static void Main(string[] args)
    {
        Thread.CurrentThread.CurrentCulture = CultureInfo.GetCultureInfo("en-US");

        Action<object> write = Console.Write;
        var sw = new Stopwatch();
        sw.Start();

        var ks = new KnapsackBruteForce
        {
            Capacity = 4,
            Items = new List<Item>
                        {
                            new Item{v = -0.1, w = -1},
                            new Item{v = 0.5, w = 1},
                            new Item{v = 1, w = 1.5},
                            new Item{v = 2.5,w = 1.5},                            
                            new Item{v = -2, w = -1},
                            new Item{v = 3, w = 2.5},
                        }.ToArray()
        };

        Data result = ks.Run();

        sw.Stop();

        write(string.Format("Capacity: {0}\n",ks.Capacity));
        write(string.Format("Items: {0}\n", ks.Items.Length));
        write(string.Format("Best value: {0}\n", result.BestValue));
        write("Include:\n");
        result.Include.ForEach(i => write(i + "\n"));
        write(string.Format("\nDuration: {0}\nPress a key to exit\n",
            sw.Elapsed.ToString()));

        Console.ReadKey();
    }
}

// O(2^n * n)
class KnapsackBruteForce
{
    public double Capacity { get; set; }
    public Item[] Items { get; set; }

    public Data Run()
    {
        var bestValue = 0d;
        var bestPosition = 0;
        var size = Items.Length;

        var permutations = (long)Math.Pow(2, size);
        for (var i = 0; i < permutations; i++)
        {
            var total = 0d;
            var weight = 0d;
            for (var j = 0; j < size; j++)
            {
                // if bit not included then skip
                if (((i >> j) & 1) != 1) continue;

                total += Items[j].v;
                weight += Items[j].w;
            }

            if (weight <= Capacity && total > bestValue)
            {
                bestPosition = i;
                bestValue = total;
            }
        }

        var include = new List<Item>();
        for (var j = 0; j < size; j++)
        {
            // if bit match then add
            if (((bestPosition >> j) & 1) == 1)
            {
                include.Add(Items[j]);
            }
        }
        return new Data { BestValue = bestValue, Include = include };
    }
}

class Item
{
    private static int _counter;
    public double Id { get; private set; }
    public double v { get; set; } // value
    public double w { get; set; } // weight
    public Item() { Id = ++_counter; }
    public override string ToString()
    {
        return string.Format("Id: {0} \tValue: {1} \tWeight: {2}",
            Id, v, w);
    }
}

class Data
{
    public List<Item> Include { get; set; }
    public double BestValue { get; set; }
}

Running this example for n = 10 gives:

Capacity: 4
Items: 10
Best value: 5.9
Include:
Id: 1   Value: -0.1     Weight: -1
Id: 2   Value: 0.5      Weight: 1
Id: 4   Value: 2.5      Weight: 1.5
Id: 6   Value: 3        Weight: 2.5

Duration: 00:00:00.0021509

Running time for various n values:

For n = 10, running time is <1 sec.
for n = 20, running time is about 1 sec.
for n = 23, running time is about 12 sec.
for n = 24, running time is about 30 sec.

The running time gets much worse from here as it increases exponentially.

Pruning

Pruning is a method to skip path of calculation when it is known that continuing that path will not succeed in a possible solution.

The pruning version can be very effective for the right range of capacity values depending on a given data set.

Pruning is better than Brute force when you need more items.
But even here it quickly slows down for n >= 40 for bad cases of combination of capacity value and data set.

program2.cs

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Globalization;
using System.Linq;
using System.Threading;


/// <summary>
/// 0-1 Knapsack pruning
/// code adapted from
/// http://stackoverflow.com/questions/8125309/0-1-knapsack-algorithm
/// </summary>
public class Program2
{
    static void Main(string[] args)
    {
        Thread.CurrentThread.CurrentCulture = CultureInfo.GetCultureInfo("en-US");
        Action<object> write = Console.Write;

        var sw = new Stopwatch();
        sw.Start();
        write("Running ..\n\n");

        var ks = new KnapsackPruning
                     {
                         Capacity = 10,
                         Items = new List<Item>
                                        {
                                             new Item {v = 0.5, w = 1},
                                             new Item {v = 1, w = 1.5},
                                             new Item {v = 1000, w = 1.5},
                                             new Item {v = 3, w = 2.5},
                                             new Item {v = 2.5, w = 2.5},
                                             new Item {v = 3, w = 3},
                                             new Item {v = 1, w = 3.5},
                                             new Item {v = 0.5, w = 1},
                                             new Item {v = 1, w = 1.5},
                                             new Item {v = 2.5, w = 1.5},
                                             
                                             new Item {v = 1000, w = 1},
                                             new Item {v = 1, w = 1.5},
                                             new Item {v = 2.5, w = 1.5},
                                             new Item {v = 3, w = 2.5},
                                             new Item {v = 2.5, w = 2.5},
                                             new Item {v = 3, w = 3},
                                             new Item {v = 1, w = 3.5},
                                             new Item {v = 0.5, w = 1},
                                             new Item {v = 1, w = 1.5},
                                             new Item {v = 2.5, w = 1.5},

                                             new Item {v = 1000, w = 1},
                                             new Item {v = 1, w = 1.5},
                                             new Item {v = 2.5, w = 1.5},
                                             new Item {v = 3, w = 2.5},
                                             new Item {v = 2.5, w = 2.5},
                                             new Item {v = 3, w = 3},
                                             new Item {v = 1, w = 3.5},
                                             new Item {v = 0.5, w = 1},
                                             new Item {v = 1, w = 1.5},
                                             new Item {v = 2.5, w = 1.5},
                                             
                                         }.ToArray()
                     };

        var result = ks.Run();

        sw.Stop();

        write(string.Format("Capacity: {0}\n", ks.Capacity));
        write(string.Format("Items: {0}\n", ks.Items.Length));
        write(string.Format("Best value: {0}\n", result.BestValue));
        write("Include:\n");
        result.Include.ForEach(i => write(i + "\n"));

        write(string.Format("\nDuration: {0}\nPress a key to exit\n",
            sw.Elapsed.ToString()));

        Console.ReadKey();
    }
}

class KnapsackPruning
{
    public double Capacity;
    public Item[] Items { get; set; }

    double _bestVal;
    bool[] _bestItems;
    int N;

    void Recursive(bool[] chosen, int depth, double w, double v, double remainingVal)
    {
        if (w > Capacity) { return; }
        if (v + remainingVal < _bestVal) { return; }
        if (depth == chosen.Length)
        {
            _bestVal = v;
            Array.Copy(chosen, _bestItems, chosen.Length);
            return;
        }

        remainingVal -= Items[depth].v;
        chosen[depth] = false;

        Recursive(chosen, depth + 1, w, v, remainingVal);

        chosen[depth] = true;
        w += Items[depth].w;
        v += Items[depth].v;

        Recursive(chosen, depth + 1, w, v, remainingVal);
    }

    public Data Run()
    {
        N = Items.Length;
        var chosen = new bool[N];
        _bestItems = new bool[N];
        _bestVal = 0;

        var totalValue = Items.Sum(i => i.v);

        Recursive(chosen, 0, 0, 0, totalValue);

        var data = new Data { BestValue = _bestVal };
        for (var i = 0; i < N; i++)
        {
            if (_bestItems[i]) { data.Include.Add(Items[i]); }
        }

        return data;
    }
}

class Item
{
    private static int _counter;
    public double Id { get; private set; }
    public double v { get; set; } // value
    public double w { get; set; } // weight
    public Item() { Id = ++_counter; }
    public override string ToString()
    {
        return string.Format("Id: {0} \tValue: {1} \tWeight: {2}",
            Id, v, w);
    }
}

class Data
{
    public List<Item> Include = new List<Item>();
    public double BestValue { get; set; }
}

For n = 30, running time is ~1 sec. (for bad choice of capacity value)
For n = 40, running time is ~10 sec. (for bad choice of capacity value)

Advertisements

Written by kunuk Nykjaer

December 27, 2012 at 12:51 am

Posted in Algorithm, Csharp

Tagged with , ,

One Response

Subscribe to comments with RSS.

  1. How this problem can be solved with ant colony algorithm?Do you have a solution?

    rebetu

    January 5, 2014 at 1:51 pm


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: