|
99 / 98 / 11
Регистрация: 12.09.2016
Сообщений: 195
|
|
Разделить N контейнеров на Q примерно равных долей20.05.2019, 15:38. Показов 1910. Ответов 8
Метки нет (Все метки)
Дано N контейнеров весом a1,a2,a3..an. Нужно распределить эти контейнеры между Q транспортными средствами так, чтобы итоговая масса груза во всех транспортных средствах была примерно одинаковой
У меня была задумка, которая заключалась в том, чтобы изначально в каждое тс класть контейнер с минимальной массой, а потом "закидывать" туда контейнер с весом максимально приближенным к разнице среднего веса всех контейнеров и текущей массой тс, но идея провалилась
1
|
|
| 20.05.2019, 15:38 | |
|
Ответы с готовыми решениями:
8
Разделить массив на два примерно равных массива Представить целое число N в виде суммы M примерно равных целых чисел. |
|
602 / 439 / 137
Регистрация: 22.11.2017
Сообщений: 1,407
|
||||||
| 20.05.2019, 17:23 | ||||||
|
Gaveyn, привет!
У меня такая идея. Я использовал принцип работы с рычажными весами в лаборатории -> про правила добавление гирек на чашу, чтобы узнать массу груза на другой чаше. На его основе построил следующий алгоритм. Спасибо, интересная задача. Кликните здесь для просмотра всего текста
1
|
||||||
|
602 / 439 / 137
Регистрация: 22.11.2017
Сообщений: 1,407
|
|
| 20.05.2019, 17:31 | |
|
Вот ещё скрины работы программы.
1
|
|
|
602 / 439 / 137
Регистрация: 22.11.2017
Сообщений: 1,407
|
||||||
| 20.05.2019, 18:05 | ||||||
|
Добавил детализацию: Какая машина какой массы грузы повезёт.
Кликните здесь для просмотра всего текста
2
|
||||||
|
602 / 439 / 137
Регистрация: 22.11.2017
Сообщений: 1,407
|
||||||
| 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,407
|
|
| 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,407
|
||
| 22.05.2019, 11:50 | ||
|
Gaveyn, пожалуйста!
Что ещё можно придумать? Самый последний способ - полный перебор всех сочетаний (очень долго).
0
|
||
| 22.05.2019, 11:50 | |
|
Помогаю со студенческими работами здесь
9
Один метод должен в новой ведомости размещать студентов в алфавитном порядке. Другой – сохранять только студентов с долей оценок (равных заданной оц
Разделить блок, например <div> на три равных станицы Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |
|
Новые блоги и статьи
|
|||
|
AkelPad-скрипты, структуры, и немного лирики..
testuser2 05.04.2026
Такая программа, как AkelPad существует уже давно, и также давно существуют скрипты под нее. Тем не менее, прога живет, периодически что-то не спеша дополняется, улучшается. Что меня в первую очередь. . .
|
Отображение реквизитов в документе по условию и контроль их заполнения
Maks 04.04.2026
Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеСпецтехники", разработанного в конфигурации КА2.
Данный документ берёт данные из другого нетипового документа. . .
|
Фото всей Земли с борта корабля Orion миссии Artemis II
kumehtar 04.04.2026
Это первое подобное фото сделанное человеком за 50 лет. Снимок называют новым вариантом легендарной фотографии «The Blue Marble» 1972 года, сделанной с борта корабля «Аполлон-17». Новое фото. . .
|
Вывод диалогового окна перед закрытием, если документ не проведён
Maks 04.04.2026
Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2.
Задача: реализовать программный контроль на предмет проведения документа. . .
|
|
Программный контроль заполнения реквизитов табличной части документа
Maks 02.04.2026
Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2.
Задача:
1. Реализовать контроль заполнения реквизита. . .
|
wmic не является внутренней или внешней командой
Maks 02.04.2026
Решение:
DISM / Online / Add-Capability / CapabilityName:WMIC~~~~
Отсюда: https:/ / winitpro. ru/ index. php/ 2025/ 02/ 14/ komanda-wmic-ne-naydena/
|
Программная установка даты и запрет ее изменения
Maks 02.04.2026
Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2.
Задача: при создании документов установить период списания автоматически. . .
|
Вывод данных в справочнике через динамический список
Maks 01.04.2026
Реализация из решения ниже выполнена на примере нетипового справочника "Спецтехника" разработанного в конфигурации КА2.
Задача: вывести данные из ТЧ нетипового документа. . .
|