# Software Programming

Kunuk Nykjaer

## 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 , ,

### 3 Responses

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

January 5, 2014 at 1:51 pm

2. Hi Kunuk,
Can you explain the code on line 72:
// if bit not included then skip
if (((i >> j) & 1) != 1) continue;
Or how to identify not including for total. Zafrul Hassan

June 26, 2018 at 12:57 am

3. I do believe all the concepts you’ve presented in your post.
They’re really convincing and will definitely work. Still, the posts are too brief for beginners.
Could you please prolong them a bit from next time?
Thanks for the post.

please click the next post (Joseph)
http://www.rentacasas.com.mx/?a=6533 find out here

January 14, 2019 at 10:44 am