Saturday, 25 November 2017

0-1 Knapsack implementation in C#

public static int Knapsack(IEnumerable<Tuple<int, int>> weightValue,
                                int capacity)
{
    var weights = weightValue.Select(t => t.Item2).ToArray();
    var values = weightValue.Select(t => t.Item1).ToArray();
    int[,] dp = new int[weightValue.Count()+1, capacity+1];
   
    //for 0 items total value is zero
    for (int i = 0; i <= capacity; i++)
    {
        dp[0, i] = 0;
    }
    //for 0 weight total value is zero
    for (int i = 0; i <= weightValue.Count(); i++)
    {
        dp[i, 0] = 0;
    }

    for (int i = 0; i <= weightValue.Count(); i++)
    {
        for (int w = 0; w <= capacity; w++)
        {
            if (weights[i] <= w)
            {
                dp[i, w] = Max(dp[i-1, w], dp[i, w-weights[i]]+values[i]);
            }
            else
            {
                dp[i, w] = dp[i-1, w];
            }
        }
    }

    return dp[weightValue.Count(), capacity];
}

No comments:

Post a Comment