Knapsack C# implementation task

Question

I'm trying to write knapsack c# algorithm with given conditions but there's always two problems i encountering. I'm getting "Index was outside the bounds of the array" error or my result is just 0.

I found couple code examples of Knapsack implementation and just can't figure out what I'm doing wrong.

Code examples: https://www.programmingalgorithms.com/algorithm/knapsack-problem

http://www.csharpstar.com/csharp-knapsack-problem/

My code:

static int Knapsack(int n, int w, int[] s, int[] v)
{
    int[,] G = new int[n+1,w+1];
    for (int k = 0; k <= n; k++)
    {
        for (int r = 0; r < w; r++)
        {
            if (r == 0 || k == 0)
                G[k, r] = 0;
            else if (s[k] <= r)
                G[k, r] = Math.Max(G[k- 1, r], v[k] + G[k - 1, r - s[k]]);
            else
                G[k, r] = G[k - 1, r]; 
        }
    }
    return G[n, w];
}
static void Main(string[] args)
{
    int[] s = { 60, 100, 120};
    int[] v = { 10, 20, 30 };
    int w = 50;
    int n = s.Length;
    Console.WriteLine(Knapsack(n, w, s, v));
}

In this case my result is 0.

Answer 1

The issue with your code is that s is the weights and v is the values and your weights of 60, 100, and 120 will obvious not fit into a capacity of 50, that's why you get a result of 0. The example you pull those values from set's the 60, 100, and 120 as the values and 10, 20, and 30 as the weights which is why it gets a result of 220.

I think this works better if you create a class to handle the related weight and value for the items.

public class Item
{
    public int Weight { get; set; }
    public int Value { get; set; }
}

Then the method only needs an array of items and the desired capacity. Also using meaningful names can make understanding what's going on easier than a bunch of single letter names.

public static int KnapSack(Item[] items, int capacity)
{
    int[,] matrix = new int[items.Length + 1, capacity + 1];
    for (int itemIndex = 0; itemIndex <= items.Length; itemIndex++)
    {
        // This adjusts the itemIndex to be 1 based instead of 0 based
        // and in this case 0 is the initial state before an item is
        // considered for the knapsack.
        var currentItem = itemIndex == 0 ? null : items[itemIndex - 1];
        for (int currentCapacity = 0; currentCapacity <= capacity; currentCapacity++)
        {
            // Set the first row and column of the matrix to all zeros
            // This is the state before any items are added and when the
            // potential capacity is zero the value would also be zero.
            if (currentItem == null || currentCapacity == 0)
            {
                matrix[itemIndex, currentCapacity] = 0;
            }
            // If the current items weight is less than the current capacity
            // then we should see if adding this item to the knapsack 
            // results in a greater value than what was determined for
            // the previous item at this potential capacity.
            else if (currentItem.Weight <= currentCapacity)
            {
                matrix[itemIndex, currentCapacity] = Math.Max(
                    currentItem.Value 
                        + matrix[itemIndex - 1, currentCapacity - currentItem.Weight],
                    matrix[itemIndex - 1, currentCapacity]);
            }
            // current item will not fit so just set the value to the 
            // what it was after handling the previous item.
            else
            {
                matrix[itemIndex, currentCapacity] = 
                    matrix[itemIndex - 1, currentCapacity];
            }
        }
    }

    // The solution should be the value determined after considering all
    // items at all the intermediate potential capacities.
    return matrix[items.Length, capacity];
}

Then running this code

var items = new[]
{
    new Item {Value = 60, Weight = 10},
    new Item {Value = 100, Weight = 20},
    new Item {Value = 120, Weight = 30},
};

Console.WriteLine(KnapSack(items, 50));

results in 220.

Here's a solution that uses recursion.

public static int KnapSackRecursive(Item[] items, int capacity)
{
    // If there are no items or capacity is 0 then return 0
    if (items.Length == 0 || capacity == 0) return 0;

    // If there is one item and it fits then return it's value
    // otherwise return 0
    if (items.Length == 1)
    {
        return items[0].Weight < capacity ? items[0].Value : 0;
    }

    // keep track of the best value seen.
    int best = 0;
    for (int i = 0; i < items.Length; i++)
    {
        // This is an array of the other items.
        var otherItems = items.Take(i).Concat(items.Skip(i + 1)).ToArray();

        // Calculate the best value without using the current item.
        int without = KnapSackRecursive(otherItems, capacity);
        int with = 0;

        // If the current item fits then calculate the best value for
        // a capacity less it's weight and with it removed from contention
        // and add the current items value to that.
        if (items[i].Weight <= capacity)
        {
            with = KnapSackRecursive(otherItems, capacity - items[i].Weight) 
                + items[i].Value;
        }

        // The current best is the max of the with or without.
        int currentBest = Math.Max(without, with);

        // determine if the current best is the overall best.
        if (currentBest > best)
            best = currentBest;
    }

    return best;
}