Распределить множество значений по строкам массива с учётом ограничения - 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; } } }
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д