Алгоритм: Как выплатить заданную сумму денюжек за минимальный набор монеток? - C#

Узнай цену своей работы

Формулировка задачи:

Собственно задач 2, но они вроде как схожие(если я неправ, придется разбить на 2 темы). 1) Есть набор монеток 1,2,5,10,25,50 копеек. Как выплатить заданную сумму денюжек за минимальный набор монеток? 2) Есть набор отрезков, заданный массивом. Отрезки самой разной длины, их очень много, могут повторяться. Как из этого массива выбрать поднабор отрезков, чтобы их сумма была как можно ближе к заданному числу(длине отрезка, который нужно получить "склеиванием" из заданных)?

Решение задачи: «Алгоритм: Как выплатить заданную сумму денюжек за минимальный набор монеток?»

textual
Листинг программы
    class Program
    {
        static int[,] Pc;
        static int N, LNeed, dL, LSum;
        static bool Find;
        static void Main(string[] args)
        {
            Console.Write("Количество отрезков: ");
            N = Int32.Parse(Console.ReadLine());
            Pc = new int[N, 3];
            Random rd = new Random();
            for (int i = 0; i < N; i++)
            {
                Pc[i, 0] = rd.Next(1, 11);
                dL += Pc[i, 0];
                Console.WriteLine("{0,2} - {1,2}", i + 1, Pc[i, 0]);
            }
            Console.Write("Необходимая длина, не более {0}: ", dL);
            LNeed = Int32.Parse(Console.ReadLine());
            Calc(0);
            LSum = 0;
            for (int i = 0; i < N; i++)
            if (Pc[i, 2] > 0)
            {
                Console.WriteLine("{0,2} - {1,2}", i + 1, Pc[i, 0]);
                LSum += Pc[i, 0];
            }
            Console.WriteLine("Итого: {0}, расхождение {1}", LSum, dL);
            Console.ReadKey(true);
        }
        static void Calc(int k)
        {
            for (int i = 0; i < 2 && !Find; i++)
            {
                Pc[k, 1] = i;
                if (i > 0)
                {
                    LSum += Pc[k, 0];
                    int l = Math.Abs(LSum - LNeed);
                    if (l < dL)
                    {
                        for (int j = 0; j < N; j++) Pc[j, 2] = Pc[j, 1];
                        dL = l;
                        if (l == 0){ Find = true; break; }
                    }
                }
                if (k < N - 1) Calc(k + 1);
            }
            Pc[k, 1] = 0;
            LSum -= Pc[k, 0];
        }
    }

Оцени полезность:

6   голосов , оценка 3.833 из 5
Похожие ответы