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