Software Programming

Kunuk Nykjaer

with one comment

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;

/// <summary>
/// Author: Kunuk Nykjaer
/// 0-1 Knapsack brute force
/// http://stackoverflow.com/questions/8125309/0-1-knapsack-algorithm
/// </summary>
public class Program
{
static void Main(string[] args)
{

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

}
}

// 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)
{
}
}
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;

/// <summary>
/// 0-1 Knapsack pruning
/// http://stackoverflow.com/questions/8125309/0-1-knapsack-algorithm
/// </summary>
public class Program2
{
static void Main(string[] args)
{
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()));

}
}

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++)
{
}

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)

Written by kunuk Nykjaer

December 27, 2012 at 12:51 am

Posted in Algorithm, Csharp

Tagged with , ,