Solution for promotion for EPOS C#

promotion_solution_knapsack_01.cs

using System;
using System.Collections.Generic;
using System.Linq;

namespace KnapsackForPromotion
{
    //Idea:
    //1. Sort the list by input descending (this is for the case we found (7,5) and (6,6) but we pick (6,6))
    //2. Get all inputs of the list item after sorted
    //3. Get indexes list of item want to pick
    //4. For each index in the list, get item at that index

    //Time complexcity Worst case: O(N * Sum). N is the length of the array. Sum is the total value of the array
    //Space Complexity: O[N][Sum]
    class Item
    {
        public char name { get; set; }
        public int cost { get; set; }
    }

    class Program
    {

        static List<int> findAllItemIndexInKnapSack(int W, List<Item> items)
        {
            int i, w;
            var sortedList = items.OrderByDescending(o => o.cost).ToList();
            var values = sortedList.Select(item => item.cost).ToList();

            var n = items.Count;
            var sum = values.Sum();
            int[,] K = new int[n + 1, sum + 1];

            if (sum < W) return new List<int>();

            for (i = 0; i <= n; i++)
            {
                for (w = 0; w <= sum; w++)
                {
                    if (i == 0 || w == 0)
                        K[i, w] = 0;
                    else if (values[i - 1] <= w)
                        K[i, w] = Math.Max(values[i - 1] +
                                K[i - 1, w - values[i - 1]], K[i - 1, w]);
                    else
                        K[i, w] = K[i - 1, w];
                }
            }

            var validSum = 0;
            var foundValidSum = false;
            for (int j = sum; j > 0; j--)
            {
                if (K[n, j] > W)
                {
                    if (K[n, j] % W == 0)
                    {
                        validSum = K[n, j];
                        foundValidSum = true;
                    }
                    if (foundValidSum == false)
                    {
                        validSum = K[n, j];
                    }
                }
                else if (K[n, j] == W)
                {
                    validSum = K[n, j];
                }
            }

            // Uncomment this block to see DP matrix
            //Console.Write("\n");
            //for (int j = 0; j <= n; j++)
            //{
            //    for (int k = 0; k <= sum; k++)
            //    {
            //        Console.Write(K[j,k] + " ");
            //    }
            //    Console.Write("\n");
            //}

            List<int> itemIndexes = new List<int>();
            for (i = n; i > 0 && validSum > 0; i--)
            {
                if (validSum == K[i - 1, validSum])
                    continue;
                else
                {
                    itemIndexes.Add(i - 1);
                    validSum -= values[i - 1];
                }
            }
            Console.WriteLine("");
            
            
            foreach (int k in itemIndexes)
            {
                Console.WriteLine(sortedList[k].name + " " + sortedList[k].cost);
            }
            
            return itemIndexes;
        }

        static void printInput(List<Item> itemList)
        {
            foreach (Item i in itemList)
            {
                Console.WriteLine(i.name + " " + i.cost);
            }
        }

        static void Main(string[] args)
        {
            var W = 12;

            Console.WriteLine("Input 1:");
            var list1 = new List<Item>()
            {
                new Item{name = 'A', cost= 3 },
                new Item{name = 'B', cost= 5 },
                new Item{name = 'C', cost= 1 },
                new Item{name = 'D', cost= 6 },
                new Item{name = 'E', cost= 2 },

            };
            printInput(list1);
            Console.Write("Result 1:");
            findAllItemIndexInKnapSack(W, list1);
            
      
            Console.WriteLine("\n\n");

            Console.WriteLine("Input 2:");
            var list2 = new List<Item>()
            {
                new Item{name = 'A', cost= 3 },
                new Item{name = 'B', cost= 5 },
                new Item{name = 'C', cost= 7 },
                new Item{name = 'D', cost= 6 },
                new Item{name = 'E', cost= 6 },

            };
            printInput(list2);
            Console.Write("Result 2:");
             findAllItemIndexInKnapSack(W, list2);
   

            Console.WriteLine("\n\n");


            Console.WriteLine("Input 3:");
            var list3 = new List<Item>()
            {
                new Item{name = 'A', cost= 6},
                new Item{name = 'B', cost= 6 },
                new Item{name = 'C', cost= 7 },
                new Item{name = 'D', cost= 4 },
                new Item{name = 'E', cost= 5 },

            };
            printInput(list3);
            Console.Write("Result 3:");
            findAllItemIndexInKnapSack(W, list3);

            Console.WriteLine("\n\n");

            Console.WriteLine("Input 4:");
            var list4 = new List<Item>()
            {
                new Item{name = 'A', cost= 11},
                new Item{name = 'B', cost= 4},
                new Item{name = 'C', cost= 4 },
                new Item{name = 'D', cost= 5 },
                new Item{name = 'E', cost= 6 },

            };
            printInput(list4);
            Console.Write("Result 4:");
            findAllItemIndexInKnapSack(W, list4);

            Console.WriteLine("\n\n");

            Console.WriteLine("Input 5:");
            var list5 = new List<Item>()
            {
                new Item{name = 'A', cost= 6},
                new Item{name = 'B', cost= 7},
                new Item{name = 'C', cost= 8 },
                new Item{name = 'D', cost= 1 },
                new Item{name = 'E', cost= 1 },

            };
            printInput(list5);
            Console.Write("Result 5:");
            findAllItemIndexInKnapSack(W, list5);
        
            Console.WriteLine("\n\n");

            Console.WriteLine("Input 6:");
            var list6 = new List<Item>()
            {
                new Item{name = 'A', cost= 6},
                new Item{name = 'B', cost= 6},
                new Item{name = 'C', cost= 6 },
                new Item{name = 'D', cost= 6 },
                new Item{name = 'E', cost= 6 },

            };
            printInput(list6);
            Console.Write("Result 6:");
            findAllItemIndexInKnapSack(W, list6);
        }
    }
}