GreedyKnapsackTest.cs

Program.cs

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

namespace GreedyKnapsack
{
    class Program
    {
        static void Main(string[] args)
        {
            Dictionary<int, int> noteInventory = new Dictionary<int, int>();
            noteInventory.Add(500, 2);
            noteInventory.Add(100, 3);
            noteInventory.Add(20, 3);

            MakeChange(620, ref noteInventory);
            Console.ReadLine();
        }

        private static void MakeChange(int change, ref Dictionary<int, int> noteInventory)
        {
            Dictionary<int, int> ChangeResult = new Dictionary<int, int>();
            while (change > 0)
            {
                var notePick = noteInventory
                    .Select(x => new KeyValuePair<int, double>(x.Key, (double)change / (double)x.Key))
                    .OrderBy(v => Math.Floor(v.Value))
                    .Where(d => d.Value >= 1);

                if (notePick != null && notePick.Count() > 0)
                {
                    var note = notePick.First();
                    var pickedNoteCount = ((int)note.Value > noteInventory[note.Key] ? noteInventory[note.Key] : (int)note.Value);
                    noteInventory[note.Key] = noteInventory[note.Key] - pickedNoteCount;
                    change = change - pickedNoteCount * note.Key;
                    ChangeResult[note.Key] = pickedNoteCount;
                }
                else
                {
                    Console.WriteLine("Not Possible bruh");
                    break;
                }
            }

            if (change == 0)
            {
                Console.WriteLine("Yippie its done");
                Console.WriteLine("Note - Count");
                foreach (var item in ChangeResult)
                {
                    Console.WriteLine($"{item.Key} = {item.Value}");
                }
            }
        }
    }
}