Integer Knapsack Problem C#

Here is a quick and dirty C# implementation of integer knapsack problem, hope it helps to the ones who may need it. (tested with .NET 4.0)

4 sample types of items with their values and weights are given and the maximum capacity of the knapsack is given. Picking the fraction(1/4 of item 1)  of item into knapsack is not allowed. In addition, since there is an unlimited amount of items for each type, you can pick more than one item with the same type.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication1
{
    ///
    /// Cite http://sacoskun.blogspot.com if you want to use the source code!!!
    /// Knapsack problem.
    ///

    class Program
    {
        static int[][] map;
        static List items;
        static int totalCap;
        struct Item
        {
            public int Id { get; set; }
            public int Value { get; set; }
            public int Weight { get; set; }
        }
        static void Main(string[] args)
        {
            totalCap = 10;
            items = new List();
            items.Add(new Item { Id = 0, Value = 3, Weight = 2 });
            items.Add(new Item { Id = 1, Value = 4, Weight = 3 });
            items.Add(new Item { Id = 2, Value = 8, Weight = 5 });
            items.Add(new Item { Id = 3, Value = 1, Weight = 1 });

            map = new int[items.Count][];
            foreach (var item in items)
            {
                map[item.Id] = new int[totalCap + 1];
            }
            FindMaxValue(totalCap);
            PrintMap();
            PrintItems();
        }

        static int FindMaxValue(int capacity)
        {
            if (capacity <= 0)
            {
                return 0;
            }
            else
            {
                int itemId = 0;
                int maxIfCapacityNodeHasItem = 0;
                int maxFromMap = -1;
                foreach (var item in items)
                {
                    if (capacity - item.Weight >= 0)
                    {
                        maxFromMap = MaxFromMap(capacity - item.Weight); // if there is precalculated value use ti.
                        int value = item.Value + ((maxFromMap==-1)?FindMaxValue(capacity - item.Weight):maxFromMap);
                        if (value > maxIfCapacityNodeHasItem)
                        {
                            itemId = item.Id;
                            maxIfCapacityNodeHasItem = value;
                        }
                    }
                }
                int maxIfCapacityNodeIsEmpty = MaxFromMap(capacity - 1);
                maxIfCapacityNodeIsEmpty = (maxIfCapacityNodeIsEmpty==-1)?FindMaxValue(capacity - 1):maxIfCapacityNodeIsEmpty;
                if (maxIfCapacityNodeHasItem >= maxIfCapacityNodeIsEmpty)
                {
                    map[itemId][capacity] = maxIfCapacityNodeHasItem;
                    return maxIfCapacityNodeHasItem;
                }
                else
                {
                    return maxIfCapacityNodeIsEmpty;
                }
            }
        }

        static int MaxFromMap(int capacity)
        {
            for (int i = 0; i < items.Count; i++)
            {
                if (map[i][capacity] > 0)
                {
                    return map[i][capacity];
                }
            }
            return -1;
        }

        static void PrintItems()
        {
            for (int c = 0; c <= totalCap; c++)
            {
                int remainingCapacity = c;
                Console.WriteLine("For capacity:" + c + " Maximum value can be achieved by:");
                while (remainingCapacity > 0)
                {
                    bool doesCapacityHaveItems = false;
                    for (int i = 0; i < items.Count; i++)
                    {
                        if (map[i][remainingCapacity] > 0)
                        {
                            Console.Write("[Item " + i + "]");
                            remainingCapacity -= items.Single(x => x.Id == i).Weight;
                            doesCapacityHaveItems = true;
                        }
                    }
                    if (doesCapacityHaveItems == false) break;
                }
                Console.WriteLine();
            }
        }

        static void PrintMap()
        {
            Console.Write("   ");

            for (int i = 0; i <= totalCap; i++)
            {
                Console.Write(i + " ");
            }
            Console.WriteLine();
            for (int i = 0; i < items.Count; i++)
            {
                Console.Write(items[i].Id + ": ");
                for (int j = 0; j <= totalCap; j++)
                {
                    Console.Write(map[i][j] + " ");
                }
                Console.WriteLine();
            }
        }
    }
}
 

Comments

Generic Viagra said…
What an interesting affair.
Thanks a lot for sharing, in fact,this blog has been so useful for me.
Thanks once again pal!

Popular posts from this blog

Space Character Problem on IE 6, 7, and 8

AWS encryption chart (SSE-S3 vs SSE-KMS vs SSE-C)

Does Netflix work on iOS 5 Beta 4?