How to implement recursive KnapSack Algorithm in C# with real life Example – Part2

As we talked about in the last article, we used the recursive approach of KnapSack and we have had 2 drawbacks. It is heavy in running time and it is not possible to track the index of removed items. In this part, we will take the Dynamic part approach which will improve running time and help us track the item’s index.

Let’s use the same image example and the example of a list of rocks from the last article.

Her is the list:

Let’s do it.

Dynamic Programming in general builds a matrix for memorization of the calculation steps. Let’s start with illustrating the matrix of calculation.

I will create a class called it KnapsackDp. It has some similarities to our Knapsack class from the last article, with some changes.

It has a constructor that takes our rock data and the maximum allowed weight. My Data class contain a list of rock weights in gram and a reward for each rock, as you saw earlier in the rock list.

public class KnapSackDp
{
    private readonly IReadOnlyList<Data> _data;
    private readonly Result _result;

    public KnapSackDp(IReadOnlyList<Data> data, int maxWeight)
    {
        var bonus = data.Select(e => e.Value).ToArray();
        var weights = data.Select(e => e.Weight).ToArray();
        _data = data;
        _result = Calculate(maxWeight, weights, bonus, bonus.Length);
    }

    public Result Calculate()
    {
        return _result;
    }

    private Result Calculate(int weight, IReadOnlyList<int> weights, IReadOnlyList<double> values, int n)
    {
        int i;
        int w;
        double[,] matrix = new double[n + 1, weight + 1];

        for (i = 0; i <= n; i++)
        {
            for (w = 0; w <= weight; w++)
            {
                var idx = i - 1;

                if (i == 0 || w == 0)
                {
                    matrix[i, w] = 0;
                }
                else if (weights[idx] <= w)
                {
                    var a = values[idx] + matrix[idx, w - weights[idx]];
                    var b = matrix[idx, w];
                    matrix[i, w] = Max(a, b);
                }
                else
                {
                    matrix[i, w] = matrix[idx, w];
                }
            }
        }

        var result = new Result();
        double value = matrix[n, weight];
        result.Value = value;
        result.Weights = new List<Data>();

        w = weight;
        for (i = n; i > 0 && value > 0; i--)
        {
            if (w < 0 || Math.Abs(value - matrix[i - 1, w]) == 0)
            {
                continue;
            }

            var data = result.GetData(_data.ToList(), i);
            if (data != null)
            {
                result.Weights.Add(data);
            }

            value -= values[i - 1];
            w -= weights[i - 1];
        }

        return result;
    }

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

My data and result class model has dummy data as shown in the rock list.

public class Data
{
    public int Id { get; set; }
    public string Description { get; set; }
    public int Weight { get; set; }
    public double Value { get; set; }

    public Data(int id, string description, int weight, double value)
    {
        Id = id;
        Description = description;
        Value = value;
        Weight = weight;
    }

    public static List<Data> RawMaterials()
    {
        return new List<Data>
        {
            new Data(1, "Rock1", 5724, 17.74),
            new Data(2, "Rock2,9873, 37.12),
            new Data(3, "Rock3",13492, 46.14),
            new Data(4, "Rock4",7727, 30.44),
            new Data(5, "Rock5",2924, 10.64),
            new Data(6, "Rock6",1544, 5),
            new Data(7, "Rock7",7082, 28.18),
            new Data(8, "Rock8",13960, 50.82),
            new Data(9, "Rock9",6371, 22.94),
            new Data(10, "Rock10",14380, 53.2),
            new Data(11, "Rock11",19045, 58.66),
            new Data(12, "Rock12",14057, 13.72),
            new Data(13, "Rock13",7082, 28.18),
            new Data(14, "Rock14",13960, 50.82),
            new Data(15, "Rock15",6371, 22.94),
            new Data(16, "Rock16",13380, 53.2),
            new Data(17, "Rock17",19045, 58.66),
            new Data(18, "Rock18",7057, 12.72),
            new Data(19, "Rock19",19045, 58.66),
            new Data(20, "Rock20",6057, 3.72)
        };
    }
}

public class Result
{
    public List<Data>? Weights { get; set; }
    public IOrderedEnumerable<Data>? Ordered => Weights?.OrderBy(e => e.Id);
    public double Value { get; set; }

    public Data? GetData(List<Data> data, int idx)
    {
        return data.Find(e => e.Id == idx);
    }
}

I will also create a config class

public static class Config
{
    public const int MaxWeight = 200000;
}

Finally, let’s run our knapsack in the main method.

public static void Main()
{
    var ks = new KnapSackDp(Config.RockData(), Config.MaxWeight);
    var calculate = ks.Calculate();

    if (calculate.Ordered == null) return;
    foreach (var data in calculate.Ordered)
    {
        Console.WriteLine(data.ToString());
    }

    if (calculate.Weights != null)
    {
        var sum = $"{calculate.Weights.Sum(e => e.Value),34:F}";
        Console.WriteLine(sum);
    }

    Console.WriteLine();

    var result = $"{calculate.Value,34:F}";
    Console.WriteLine(result);
}

When we run this method, we will get this output:

1   Rock1           5724     17,74
2   Rock2           9873     37,12
3   Rock3          13492     46,14
4   Rock4           7727     30,44
5   Rock5           2924     10,64
6   Rock6           1544      5,00
7   Rock7           7082     28,18
8   Rock8          13960     50,82
9   Rock9           6371     22,94
10  Rock10         14380     53,20
11  Rock11         19045     58,66
13  Rock13          7082     28,18
14  Rock14         13960     50,82
15  Rock15          6371     22,94
16  Rock16         13380     53,20
17  Rock17         19045     58,66
18  Rock18          7057     12,72
19  Rock19         19045     58,66
20  Rock20          6057      3,72
                            649,78

As we can see, all items are included, except item 12. This is exactly what we calculated in last article. But here we have a list of item we need to pick up in our trolley.

Conclusion

As you can see, with few lines of code, knapsack algorithms are able to calculate very complex problems and complicated problems. With this approach, we get better performance and index of included items. I am pretty sure this Algorithm has a place for more performance and clean up. But this is not the intention of this article. Enjoy.