# Software Programming

Kunuk Nykjaer

## Knapsack

This is a pseudo-polynomial solution to the 0-1 Knapsack problem.

I found this good article on dynamic programming version of Knapsack. I simply adapted it to a C# version.

Recursive version
Program.cs

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

namespace Knapsack
{
/// <summary>
/// Author: Kunuk Nykjaer
/// 0-1 Knapsack in C#
/// Recursive version
/// http://www.programminglogic.com/knapsack-problem-dynamic-programming-algorithm/
/// </summary>
public class Program
{
private static void Main(string[] args)
{

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

write("Running ..\n\n");
var rand = new Random();

// --------- Insert data here
const int N = 10;
const int maxWeight = 20;
var items = new List<Item>();

for (var i = 0; i < N; i++)
{
items.Add(new Item { w = rand.Next(1, 10), v = rand.Next(1, 100) });
}
//               {
//                   new Item {w = 5, v = 10},
//                   new Item {w = 4, v = 40},
//                   new Item {w = 6, v = 30},
//                   new Item {w = 3, v = 50},
//               });

//---------

Knapsack.Init(items, maxWeight);
Knapsack.Run();

stopwatch.Stop();

write("Done\n\n");

Knapsack.PrintPicksMatrix(write);
Knapsack.Print(write,true);

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

static class Knapsack
{
static int[][] M { get; set; } // matrix
static int[][] P { get; set; } // picks
static Item[] I { get; set; } // items
public static int MaxValue { get; private set; }
static int W { get; set; } // max weight

public static void Init(List<Item> items, int maxWeight)
{
I = items.ToArray();
W = maxWeight;

var n = I.Length;
M = new int[n][];
P = new int[n][];
for (var i = 0; i < M.Length; i++) { M[i] = new int[W + 1]; }
for (var i = 0; i < P.Length; i++) { P[i] = new int[W + 1]; }
}

public static void Run()
{
MaxValue = Recursive(I.Length-1, W, 1);
}

static int Recursive(int i, int w, int depth)
{
var take = 0;
if (M[i][w] != 0) { return M[i][w]; }

if (i == 0)
{
if (I[i].w <= w)
{
P[i][w] = 1;
M[i][w] = I[0].v;
return I[i].v;
}

P[i][w] = -1;
M[i][w] = 0;
return 0;
}

if (I[i].w <= w)
{
take = I[i].v + Recursive(i - 1, w - I[i].w, depth + 1);
}

var dontTake = Recursive(i - 1, w, depth + 1);

M[i][w] = Max(take, dontTake);

if (take > dontTake) { P[i][w] = 1; }
else { P[i][w] = -1; }

return M[i][w];
}

public static void Print(Action<object> write, bool full)
{
var list = new List<Item>();
var w = W;
var i = list.Count - 1;

write(string.Format("Items: = {0}\n", list.Count));
if(full) {list.ForEach(a => write(string.Format("{0}\n", a)));}

write(string.Format("\nMax weight = {0}\n", W));
write(string.Format("Max value = {0}\n", MaxValue));
write("\nPicks were:\n");

var valueSum = 0;
var weightSum = 0;
while (i >= 0 && w >= 0)
{
if (P[i][w] == 1)
{
valueSum += list[i].v;
weightSum += list[i].w;
if(full){write(string.Format("{0}\n", list[i]));}
w -= list[i].w;
}

i--;
}
write(string.Format("\nvalue sum: {0}\nweight sum: {1}",
valueSum, weightSum));
}

public static void PrintPicksMatrix(Action<object> write)
{
write("\n\n");
foreach (var i in P)
{
foreach (var j in i)
{
var s = j.ToString();
var _ = s.Length > 1 ? " " : "  ";
write(string.Concat(s,_));
}
write("\n");
}
}

static int Max(int a, int b)
{
return a > b ? a : b;
}
}

class Item
{
private static int _counter;
public int Id { get; private set; }
public int v { get; set; } // value
public int w { get; set; } // weight
public Item()
{
Id = ++_counter;
}

public override string ToString()
{
return string.Format("Id: {0}  v: {1}  w: {2}",
Id, v, w);
}
}
}
```

Here’s is a sample result from running this code.

```Picks table

-1 1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1
-1 -1 1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1
-1 -1 -1 -1 -1 -1 -1 -1 1  1  1  1  1  1  1  1  1  1  1  1  1
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1  1  1  1  1  1  1  1  1  1
0  0  -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
0  0  0  -1 1  1  1  0  1  -1 1  1  1  1  1  1  0  -1 1  1  1
0  0  0  0  1  0  1  0  0  1  0  1  0  1  0  1  0  0  1  0  1
0  0  0  0  0  0  0  0  0  0  0  0  0  -1 0  -1 0  0  -1 0  -1
0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  -1 0  -1
0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  -1

Items: = 10
Id: 1  v: 46  w: 1
Id: 2  v: 63  w: 2
Id: 3  v: 51  w: 6
Id: 4  v: 84  w: 8
Id: 5  v: 4  w: 9
Id: 6  v: 41  w: 1
Id: 7  v: 66  w: 1
Id: 8  v: 30  w: 9
Id: 9  v: 7  w: 5
Id: 10  v: 26  w: 2

Max weight = 20
Max value = 351

Picks were:
Id: 7  v: 66  w: 1
Id: 6  v: 41  w: 1
Id: 4  v: 84  w: 8
Id: 3  v: 51  w: 6
Id: 2  v: 63  w: 2
Id: 1  v: 46  w: 1

value sum: 351
weight sum: 19

Duration: 00:00:00.0034186
```

For loop version
Program2.cs

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

namespace Knapsack
{
/// <summary>
/// Author: Kunuk Nykjaer
/// 0-1 Knapsack in C#
/// Loop version
/// http://www.programminglogic.com/knapsack-problem-dynamic-programming-algorithm/
/// </summary>
public class Program2
{
private static void Main(string[] args)
{

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

write("Running ..\n\n");
var rand = new Random();

// --------- Insert data here
const int maxWeight = 10;
const int N = 100000;
var items = new List<Item>();

for (var i = 0; i < N; i++)
{
items.Add(new Item { w = rand.Next(1, 10), v = rand.Next(1, 10000) });
}
//               {
//                   new Item {w = 5, v = 10},
//                   new Item {w = 4, v = 40},
//                   new Item {w = 6, v = 30},
//                   new Item {w = 3, v = 50},
//               });

// ---------

Knapsack.Init(items, maxWeight);
Knapsack.Run();

stopwatch.Stop();

write("Done\n\n");

// Knapsack.PrintPicksMatrix(write);
Knapsack.Print(write,false);

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

static class Knapsack
{
static int[][] M { get; set; }
static int[][] P { get; set; }
static Item[] I { get; set; }
public static int MaxValue { get; private set; }
static int W { get; set; }

public static void Init(List<Item> items, int maxWeight)
{
I = items.ToArray();
W = maxWeight;

var n = I.Length;
M = new int[n+1][];
P = new int[n+1][];
for (var i = 0; i < M.Length; i++) { M[i] = new int[W + 1]; }
for (var i = 0; i < P.Length; i++) { P[i] = new int[W + 1]; }
}

public static void Run()
{
var n = I.Length;

for (var i = 1; i <= n; i++)
{
for (var j = 0; j <= W; j++)
{
if (I[i - 1].w <= j)
{
M[i][j] = Max(M[i - 1][j], I[i - 1].v + M[i - 1][j - I[i - 1].w]);
if (I[i - 1].v + M[i - 1][j - I[i - 1].w] > M[i - 1][j])
{
P[i][j] = 1;
}
else
{
P[i][j] = -1;
}
}
else
{
P[i][j] = -1;
M[i][j] = M[i - 1][j];
}
}
}
MaxValue = M[n][W];
}

public static void Print(Action<object> write, bool all)
{
var list = new List<Item>();
var w = W;
var i = list.Count;

write(string.Format("Items: = {0}\n", list.Count));
if(all) {list.ForEach(a => write(string.Format("{0}\n", a)));}

write(string.Format("\nMax weight = {0}\n", W));
write(string.Format("Max value = {0}\n", MaxValue));
write("\nPicks were:\n");

var valueSum = 0;
var weightSum = 0;
while (i >= 0 && w >= 0)
{
if (P[i][w] == 1)
{
valueSum += list[i-1].v;
weightSum += list[i-1].w;
if(all){write(string.Format("{0}\n", list[i-1]));}

w -= list[i-1].w;
}

i--;
}
write(string.Format("\nvalue sum: {0}\nweight sum: {1}",
valueSum, weightSum));
}

public static void PrintPicksMatrix(Action<object> write)
{
write("\n\n");
foreach (var i in P)
{
foreach (var j in i)
{
var s = j.ToString();
var _ = s.Length > 1 ? " " : "  ";
write(string.Concat(s, _));
}
write("\n");
}
}

static int Max(int a, int b)
{
return a > b ? a : b;
}
}

class Item
{
private static int _counter;
public int Id { get; private set; }
public int v { get; set; } // value
public int w { get; set; } // weight
public Item()
{
Id = ++_counter;
}

public override string ToString()
{
return string.Format("Id: {0}  v: {1}  w: {2}",
Id, v, w);
}
}
}
```

Here’s is a sample result from running this code.

```Items: = 100000

Max weight = 10
Max value = 99935

Picks were:

value sum: 99935
weight sum: 10

Duration: 00:00:00.1987271
```

Written by kunuk Nykjaer

January 6, 2013 at 1:55 pm

### 4 Responses

1. It is not working right.
maxWeight = 4;
new Item {w = 3, v = 47},
new Item {w = 1, v = 14},
new Item {w = 2, v = 31},
it gives the result 61.
But should 62

Oleksii

December 22, 2013 at 4:09 pm

2. if Max weight is low , this method is well.
thank you for this share

rebetu

January 5, 2014 at 1:58 pm

3. How do I tell this script how many to take?

Tim

February 11, 2014 at 5:31 am