Распределить множество значений по строкам массива с учётом ограничения - C#

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

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

Доброе время суток! Помогите пожалуйста с разработкой алгоритма: Нужно из одномерного массива значений, например: 1050/2000/2050/2050/1050 Распределить эти значения по строкам матрицы (как вариант в ступенчатый массив), учитывая что сумма этих значений в строке не должна превышать заданного значения (скажем 4200). Так вот, как это сделать программно? В ручную делаю так: Массив: 1050/2000/2050/2050/1050 Ограничение = 4200 Тогда расчёт таким образом: 1050 + 1050 +2050 = 4150 -> минимальный остаток 50 использованные ранее значения из массива удаляем и не учитываем при дальнейших расчётах 2000 + 2050 = 4050 -> мин. остаток из оставшихся элементов 150 Т.е. матрица плана: 1050, 1050, 2050 2000, 2050 Помогите пожалуйста перевести в программный код, а то и на рекурсию думал и на перебор значений но не выходит.

Решение задачи: «Распределить множество значений по строкам массива с учётом ограничения»

textual
Листинг программы
using System;
using System.Collections.Generic;
using System.Linq;
 
namespace ConsoleApplication9
{
    class Program
    {
        static void Main(string[] args)
        {
            int max = 0;
            int[] ar = { 1050,2000,2050,2050,1050};
            bool flag = true;
            int count = 0;
            //проверка на корректный максимум
            while (flag)
            {
                Console.WriteLine("Введите максимум: ");
                max = int.Parse(Console.ReadLine());
                var a = ar.GroupBy(x => x > max);
                foreach (var val in a)
                {
                    if(val.Key)
                    count = val.Count();
                }
 
                if (count > 0)
                {
                    Console.WriteLine("Найдено {0} элементов превышающих максимум ", count);
                    count = 0;
                }
                else
                    flag = false;
            }
            //находим максимальный элемент
            List<List<int>> list = new List<List<int>>();
 
            while (ar.Length > 0)
            {
                flag = false;
                List<int> l = new List<int>();
                int maxInAr = ar.Max();
                int minInAr = ar.Min();
                int result = max - maxInAr;
                count = 0;//добавил счётчик
                while (result >= minInAr)
                {
                    flag = true;
                    if (count == 0)//максимальный элемент записывается только на входе
                    {
                        l.Add(maxInAr);
                        ar = ResizeAr(ar, maxInAr);
                    }
                    count++;
                    var newAr = ar.Where(x => x <= result).OrderBy(x => x);
                    if (newAr.Count() > 0)
                    {
                        int newMax = newAr.Max();
                        l.Add(newMax);
                        result -= newMax;
                        if (result < minInAr)
                        {
                            list.Add(l);
                        }
                        ar = ResizeAr(ar, newMax);//а тут вынес из if, т.к. ресайзить нужно и промежуточные результаты
                    }
                    else { list.Add(l); break; }
                }
                count = 0;
                if (result < minInAr &!flag)
                {
                    l.Add(maxInAr);
                    list.Add(l);
                    ar = ResizeAr(ar, maxInAr); 
                }
            }
 
            Console.WriteLine("Результат \n");
            foreach (List<int> s in list)
            { 
                string str = "[";
                foreach (int i in s)
                    str += i.ToString() + ",";
                str = str.Substring(0, str.Length - 1) + "]";
                Console.WriteLine(str);
            }
            Console.ReadKey();
        }
        static int[] ResizeAr(int[] ar, int el) 
        {
            if (ar.Length > 0)
            {
                int ind = Array.FindIndex(ar, x => x == el);
                if (ind < 0)
                    return ar;
                Array.Clear(ar, ind, 1);
                Array.Sort(ar);
                Array.Reverse(ar);
                Array.Resize(ref ar, ar.Length - 1);
            }
            return ar;
        }
    }
}

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

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

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