задача на комбинаторику

285
06 января 2018, 02:30

Решил упростить себе работу и переложить часть рутинных расчетов на программу, но простая, на первый взгляд, задача не поддается решению. Может кто-нибудь подскажет.

Есть ArrayList со случайным количеством элементов. Есть параметр int max. Все элементы в массиве уже гарантированно меньше int max. Для примера. int max=10; Ну и числа в листе(2,7,9,1,3,5,4,7,1,2,3); Нужно скомбинировать эти отрезки в группы, чтобы сумма группы была<=int max. И вывести суммы чисел этих групп.

Например
1,5,3=9;
1,4,4=9;
1,2,1,3=7;

Т.е. если сравнивать int max с коробкой а числа в листе с вещами, то нужно распихать всякий хлам в коробки максимально компактно и вывести результат. Можно java,c#,js или что-нибудь другое понятное; Если кому интересно, то отрезки - это куски труб. если есть например 3,4,5,2-х метровые куски, то нужно заказать 9 метровый кусок и 5-и метровый. Т.к. максимальная длина -10м.

Answer 1

Есть такой вариант но он кривой довольно

namespace FileRead
{
    class Program
    {
        static List<List<int>> result = new List<List<int>>();
        static int max = 10;
        static void Main(string[] args)
        {

            List<int> l = new List<int>();
            Random rnd = new Random();
            for (int i = 0; i < 12; i++)
            {
                l.Add(rnd.Next(max));
            }
            Console.WriteLine("Исходный массив");
            foreach (var item in l)
            {
                Console.Write($"{item} ");
            }
            Console.WriteLine("\n");
            Calc(l);
            Console.WriteLine("\n\n\n");
            foreach (var item in result)
            {
                foreach (var item1 in item)
                {
                    Console.Write(item1);
                }
                Console.WriteLine();
            }
            Console.Read();
        }
        static void Calc(List<int> list)
        {
            if (list.Count <= 2)
                return;
            var t = new List<int>();
            var e = list.TakeWhile(g => { t.Add(g); return t.Sum() < max; }).ToList();
            result.Add(e.ToList());
            for (int i = 0; i < e.Count; i++)
            {
                list.Remove(e[i]);
            }
            Calc(list);
        }
    }
}
READ ALSO
Сохранение объекта в базу данных с одинаковым полем

Сохранение объекта в базу данных с одинаковым полем

Есть GWT приложение, которое отправляет асинхронный запрос на серверСервер обращается к REST сервису для сохранения переданного объекта в базу...

212
онлайн средства для получения данных из макета

онлайн средства для получения данных из макета

У Adobe есть\был некий продукт, позволяющий заливать макет PSD, и после обработки получать из него всю необходимую информацию в виде цветов\шрифтов...

225
Ссылки на php страницы через Gulp

Ссылки на php страницы через Gulp

Не получается проходить по ссылкам (на php файлы) при работе через GulpВот отрывок кода файла gulpfile

216
Bootstrap и Media запросы

Bootstrap и Media запросы

Всем привет, при верстке, использую bootstrap

271