|
99 / 98 / 11
Регистрация: 12.09.2016
Сообщений: 195
|
|
Разделить N контейнеров на Q примерно равных долей20.05.2019, 15:38. Показов 1873. Ответов 8
Метки нет (Все метки)
Дано N контейнеров весом a1,a2,a3..an. Нужно распределить эти контейнеры между Q транспортными средствами так, чтобы итоговая масса груза во всех транспортных средствах была примерно одинаковой
У меня была задумка, которая заключалась в том, чтобы изначально в каждое тс класть контейнер с минимальной массой, а потом "закидывать" туда контейнер с весом максимально приближенным к разнице среднего веса всех контейнеров и текущей массой тс, но идея провалилась
1
|
|
| 20.05.2019, 15:38 | |
|
Ответы с готовыми решениями:
8
Разделить массив на два примерно равных массива Представить целое число N в виде суммы M примерно равных целых чисел. |
|
602 / 439 / 137
Регистрация: 22.11.2017
Сообщений: 1,405
|
||||||
| 20.05.2019, 17:23 | ||||||
|
Gaveyn, привет!
У меня такая идея. Я использовал принцип работы с рычажными весами в лаборатории -> про правила добавление гирек на чашу, чтобы узнать массу груза на другой чаше. На его основе построил следующий алгоритм. Спасибо, интересная задача. Кликните здесь для просмотра всего текста
1
|
||||||
|
602 / 439 / 137
Регистрация: 22.11.2017
Сообщений: 1,405
|
|
| 20.05.2019, 17:31 | |
|
Вот ещё скрины работы программы.
1
|
|
|
602 / 439 / 137
Регистрация: 22.11.2017
Сообщений: 1,405
|
||||||
| 20.05.2019, 18:05 | ||||||
|
Добавил детализацию: Какая машина какой массы грузы повезёт.
Кликните здесь для просмотра всего текста
2
|
||||||
|
602 / 439 / 137
Регистрация: 22.11.2017
Сообщений: 1,405
|
||||||
| 20.05.2019, 19:09 | ||||||
|
Gaveyn, оптимизировал и причесал код.
Кликните здесь для просмотра всего текста
1
|
||||||
|
99 / 98 / 11
Регистрация: 12.09.2016
Сообщений: 195
|
|
| 20.05.2019, 20:37 [ТС] | |
|
SomniPhobia, а можешь, пожалуйста, сам принцип алгоритма рассказать?
0
|
|
|
602 / 439 / 137
Регистрация: 22.11.2017
Сообщений: 1,405
|
|
| 21.05.2019, 10:05 | |
Сообщение было отмечено Gaveyn как решение
Решение
Gaveyn, привет!
Могу. Принцип работы с рычажными весами. На одной чаше лежит груз, массу которого необходимо узнать. Вторая чаша для гирек пока пуста. Правило постановки гирь на чашу такого: Сперва ставим самую тяжёлую гирю что есть. Если она перевешивает груз, то снимаем её с чаши и ставим следующую по убыванию массы гирю. Тоже перевешивает - снимаем с чаши и ставим полегче и т. д. Как только гиря перестала перевешивать груз (чаша весов с грузом опустилась хоть и поставили гирю), берём следующую по убыванию массы гирю и кладём её рядом к первой. И так подбираем по убыванию вторую гирю пока груз не перевесит две гири. Всё сводится к тому, чтобы дойти до самых лёгких гирек что есть (или до требуемой точности измерения), пытаясь выровнять положение чаш весов друг напротив друга. Алгоритм в коде. За основу взят принцип работы с рычажными весами, но он был модернизирован. Собираем все массы грузов в контейнер boxes. Сортируем его по убыванию массы грузов (левый самый тяжёлый, правый самый лёгкий). Затем проходим по этому контейнеру, содержащему массы грузов по убыванию. Первый груз (самый тяжёлый) грузим на первое транспортное средство (далее по тексту как ТС), следующий груз в контейнере boxes чуть полегче грузим на второе ТС, чуть полегче на 3 ТС и т. д. Сколько у нас ТС задано (значение переменной q), столько ТС и нагружается. Принцип таков. Контейнер transport_total_mass изначально содержит нули в количестве q. То есть изначально каждое ТС везёт 0 единиц массы. Нагружаем так: ищем ТС, у которого минимальная масса груза. В него грузим очередной груз как можно большей массы. Загрузили. Снова ищем минимум. Туда загружаем груз полегче. Снова ищем минимум по контейнеру transport_total_mass. То есть то ТС, которое загружено меньше остальных. Туда груз загружаем полегче. Пример Всего ТС 3 Есть грузы массой 1 2 3 4 5 10 8 Сортировка 10 8 5 4 3 2 1 До распределения содержание контейнера transport_total_mass 0 0 0 Распределение Проход 0 (в руках груз массой 10) 10 0 0 Проход 1 (в руках груз массой 8) 10 8 0 Проход 2 (в руках груз массой 5) 10 8 5 Проход 3 (в руках груз массой 4) 10 8 9 Проход 4 (в руках груз массой 3) 10 11 9 Проход 5 (в руках груз массой 2) 10 11 11 Проход 6 (в руках груз массой 1) 11 11 11 Итог распределения 11 11 11 Принцип понятен?
1
|
|
|
99 / 98 / 11
Регистрация: 12.09.2016
Сообщений: 195
|
|
| 21.05.2019, 22:59 [ТС] | |
|
SomniPhobia, Спасибо большое, очень помогли разобраться!
Добавлено через 2 часа 43 минуты SomniPhobia, Извините, а вы уверены что этот алгоритм работает всегда? Я ввел Q = 2, а далее N = { 8 13 16 18 14 12} По-идее должно быть Q1 = { 8+18+14 } , а Q2 = { 13+16+12}, тогда получилось бы что первый повезет груз массой 40, а второй повезет груз массой 41. (разница в 1) Ваша же программа предлагает распределить так: Q1= { 18+13+8}, Q2 = {16+14+12}. Тогда один повезет груз массой 39, а другой массой 42 (разница 3)
1
|
|
|
602 / 439 / 137
Регистрация: 22.11.2017
Сообщений: 1,405
|
||
| 22.05.2019, 11:50 | ||
|
Gaveyn, пожалуйста!
Что ещё можно придумать? Самый последний способ - полный перебор всех сочетаний (очень долго).
0
|
||
| 22.05.2019, 11:50 | |
|
Помогаю со студенческими работами здесь
9
Один метод должен в новой ведомости размещать студентов в алфавитном порядке. Другой – сохранять только студентов с долей оценок (равных заданной оц
Разделить блок, например <div> на три равных станицы Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |
|
Новые блоги и статьи
|
||||
|
Access
VikBal 11.12.2025
Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.
|
Новый ноутбук
volvo 07.12.2025
Всем привет.
По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне:
Ryzen 5 7533HS
64 Gb DDR5
1Tb NVMe
16" Full HD Display
Win11 Pro
|
Музыка, написанная Искусственным Интеллектом
volvo 04.12.2025
Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .
|
От async/await к виртуальным потокам в Python
IndentationError 23.11.2025
Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
|
Поиск "дружественных имён" СОМ портов
Argus19 22.11.2025
Поиск "дружественных имён" СОМ портов
На странице:
https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/
нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .
|
|
Сколько Государство потратило денег на меня, обеспечивая инсулином.
Programma_Boinc 20.11.2025
Сколько Государство потратило денег на меня, обеспечивая инсулином.
Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов.
. . .
|
Ломающие изменения в C#.NStar Alpha
Etyuhibosecyu 20.11.2025
Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .
|
Мысли в слух
kumehtar 18.11.2025
Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .
|
Создание Single Page Application на фреймах
krapotkin 16.11.2025
Статья исключительно для начинающих. Подходы оригинальностью не блещут.
В век Веб все очень привыкли к дизайну Single-Page-Application .
Быстренько разберем подход "на фреймах".
Мы делаем одну. . .
|
Фото: Daniel Greenwood
kumehtar 13.11.2025
|