Knapsack Problem in C#

Let’s say, you have some items to be packed in a space limited duffel bag. As you can’t pack everything, you prefer to take only the valuable items. At least this is what we do when we are heading for a holiday in a tropical island. This is a classic knapsack problem where we can use dynamic programming approach to prevent exponential running time. There are plenty of materials in web that explain how this algorithm works. A good video tutorial is available on youtube (http://www.youtube.com/watch?v=EH6h7WA7sDw )

However, as I didn’t find any C# implementation of Knapsack problem I thought of writing a small code that demonstrate how to tackle this problem.

Here is the code for that.

static void Main(string[] args)
{

    Item a = new Item(1, 3, 5);
    Item b = new Item(2, 2, 3);
    Item c = new Item(3, 1, 4);

    List<Item> items = new List<Item>();
    items.Add(a);
    items.Add(b);
    items.Add(c);
    int BagCapacity = 5;

    KnapSackProblem problem=new KnapSackProblem();

    int totalValueOfItems = 0;
    List<Item> itemsToBePacked = problem.FindItemsToPack(items, BagCapacity, out totalValueOfItems);
}

 

class KnapSackProblem
{

    public List<Item> FindItemsToPack(List<Item> items, int capacity,out int totalValue)
    {
       
        int[,] price = new int[items.Count + 1, capacity + 1];
        bool[,] keep = new bool[items.Count + 1, capacity + 1];

        for (int i = 1; i <= items.Count; i++)
        {
            Item currentItem = items[i - 1];
            for (int space = 1; space <= capacity; space++)
            {
                if (space >= currentItem.Weight)
                {
                    int remainingSpace = space - currentItem.Weight;
                    int remainingSpaceValue = 0;
                    if (remainingSpace > 0)
                    {
                        remainingSpaceValue = price[i - 1, remainingSpace];
                    }
                    int currentItemTotalValue = currentItem.Price + remainingSpaceValue;
                    if (currentItemTotalValue > price[i - 1, space])
                    {
                        keep[i, space] = true;
                        price[i, space] = currentItemTotalValue;
                    }
                    else
                    {
                        keep[i, space] = false;
                        price[i, space] = price[i - 1, space];
                    }
                }
            }
        }

        List<Item> itemsToBePacked = new List<Item>();

        int remainSpace = capacity;
        int item = items.Count;
        while (item > 0)
        {
            bool toBePacked = keep[item, remainSpace];
            if (toBePacked)
            {
                itemsToBePacked.Add(items[item - 1]);
                remainSpace = remainSpace - items[item - 1].Weight;
            }
            item--;
        }

        totalValue = price[items.Count,capacity];
        return itemsToBePacked;
    }

}

 

public class Item
{
    public int ID;
    public int Weight;
    public int Price;
    public Item(int id, int weight, int value)
    {
        this.ID = id;
        this.Weight = weight;
        this.Price = value;
    }
    public override string ToString()
    {
        return "ID="+ID+",W=" + Weight + ",V=" + Price;
    }
}

 

Hopefully this will save some of your programming time!