Software Programming

Kunuk Nykjaer

0-1 Knapsack dynamic programming with C#

with 4 comments


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;
using System.Threading;

namespace Knapsack
{
    /// <summary>
    /// Author: Kunuk Nykjaer
    /// 0-1 Knapsack in C#
    /// Recursive version
    /// code adapted from
    /// http://www.programminglogic.com/knapsack-problem-dynamic-programming-algorithm/
    /// </summary>
    public class Program
    {
        private static void Main(string[] args)
        {
            Thread.CurrentThread.CurrentCulture = CultureInfo.GetCultureInfo("en-US");

            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) });
            }
            //items.AddRange(new List<Item>
            //               {
            //                   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()));
            Console.ReadKey();
        }
    }

    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>();
            list.AddRange(I);
            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;
using System.Threading;

namespace Knapsack
{
    /// <summary>
    /// Author: Kunuk Nykjaer
    /// 0-1 Knapsack in C#
    /// Loop version
    /// code adapted from
    /// http://www.programminglogic.com/knapsack-problem-dynamic-programming-algorithm/
    /// </summary>
    public class Program2
    {
        private static void Main(string[] args)
        {
            Thread.CurrentThread.CurrentCulture = CultureInfo.GetCultureInfo("en-US");

            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) });
            }
            //items.AddRange(new List<Item>
            //               {
            //                   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()));
            Console.ReadKey();
        }
    }

    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>();
            list.AddRange(I);
            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
Advertisements

Written by kunuk Nykjaer

January 6, 2013 at 1:55 pm

4 Responses

Subscribe to comments with RSS.

  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


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: