Knapsack Problem

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

namespace _01KnapsackProblem
{
    class Program
    {
        static void Main(string[] args)
        {
            List<Item> items = new List<Item>();
            items.Add(new Item("NoCost", int.MaxValue, 0));
            items.Add(new Item("beer", 3, 2));
            items.Add(new Item("vodka", 8, 12));
            items.Add(new Item("cheese", 4, 5));
            items.Add(new Item("nuts", 1, 4));
            items.Add(new Item("ham", 2, 3));
            items.Add(new Item("whiskey", 8, 13));


            int totalCost = 0;
            List<int> result = Calculate(items, 10, out totalCost);
            Console.WriteLine("Optimal Solution");
            for (int i = 0; i < result.Count; i++)
            {
                Console.WriteLine(items[result[i]].Name);
            }
            Console.WriteLine("Cost = {0}", totalCost);
        }

        private static List<int> Calculate(List<Item> items, int maxWeight, out int cost)
        {
            int N = items.Count;
            List<int>[,] optimalValues = new List<int>[N+1, maxWeight + 1];
            int[,] optimalCost = new int[N+1, maxWeight + 1];
            for (int i = 0; i < items.Count; i++)
            {
                optimalValues[i, 0] = new List<int>();
            }

            for (int i = 1; i < N; i++)
            {
                for (int weight = 1; weight <= maxWeight; weight++)
                {
                    if (weight >= items[i].Weight)
                    {
                        if (items[i].Cost + optimalCost[i - 1, weight - items[i].Weight]
                            > optimalCost[i - 1, weight])
                        {
                            optimalCost[i, weight] = items[i].Cost +
                                optimalCost[i - 1, weight - items[i].Weight];
                            optimalValues[i, weight] = new List<int>();
                            optimalValues[i, weight].Add(i);
                            if (optimalValues[i - 1, weight - items[i].Weight] != null)
                            {
                                optimalValues[i, weight].AddRange(optimalValues[i - 1, weight - items[i].Weight]);
                            }
                        }
                        else
                        {
                            optimalCost[i, weight] = optimalCost[i - 1, weight];
                            optimalValues[i, weight] = optimalValues[i - 1, weight];
                        }
                    }
                    else
                    {
                        optimalCost[i, weight] = optimalCost[i - 1, weight];
                        optimalValues[i, weight] = optimalValues[i - 1, weight];
                    }
                }
            }
            cost = optimalCost[N - 1, maxWeight];

            return optimalValues[N - 1, maxWeight];
        }
    }
}