Алгоритм поиска вариантов распределения X ресурсов по N складам, каждый из которых имеет емкость Y

@Rockedit · Регистрация: 22.12.2009

Студворк — интернет-сервис помощи студентам

Всем привет!
Решаю следушую задачу.
Имеется пользователь с потребностью в X ресурсах. Имеется N складов, на каждом из которых Y ресурсов. Мне нужно получить все варианты, получения пользователем X ресурсов с N складов.
Пример
Пользователю нужно 6 ед. ресурсов. Есть 2 склада с 6 и 7 ресурсами
Варианты
1 склад 2 склад
6 0
5 1
4 2
3 3
2 4
1 5
6 0
Это элементарный пример. На самом деле задача может быть гораздо сложнее, скажем может быть 200 складов, и тогда вариантов очень много.
У кого какие идеи как этот процесс можно автоматизировать?
Заранее всем спасибо!

@XAHOK · 12.04.2011, 13:34

Нечто подобное делал для поиска наиболее оптимального набора действий.
Формировал дерево событий, если применительно к твоей задаче, то:
Корневые элементы - из склада 1 взято 0 единиц, вложенные узлы из склада 2 взяты 0,1,2...n единиц
- из склада 1 взято 1 единиц, вложенные узлы из склада 2 взяты 0,1,2...n-1 единиц
- из склада 1 взято 2 единиц, вложенные узлы из склада 2 взяты 0,1,2...n-2 единиц
- из склада 1 взято ...
Для узлов второго склада аналогично формируется список возможных заборов из склада 3 и т.д. В такой постановке при необходимости легко реализовать многопоточный перебор.
Для дополнительной оптимизации можно на этапе формирования каждого слоя находить эквивалентные объемы оставшейся продукции и коллапсировать эти ветки в одну.

@Rockedit · 12.04.2011, 14:25 **[ТС]**

Спасибо. идея очень хорошая!

Добавлено через 42 минуты
Интересно, а как получить все комбинации. к примеру 3 склада с запасами 1 2 2, варианты
0 0 0
0 0 1
0 0 2
0 1 0
0 1 1
0 1 2
0 2 0
0 2 1
0 2 2
1 0 0
1 0 1
1 0 2
1 1 0
1 1 1
1 1 2
1 2 0
1 2 1
1 2 2
а как получить тоже самое для n складов?

@XAHOK · 12.04.2011, 15:30

В каждом узле добавлять дополнительные списки по количеству дочерних узлов минус 1. Добавляем в уже существующий значение нулевого узла, а в остальные копируем данные о пути + соответствующий дочерний узел. Получаем нечто наподобие прохождения фронта волны.

@nikita2501 · 12.12.2017, 19:08

Можете отправить готовую программу?

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий 8Observer8 02.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11680&d=1772460536 Одним из. . .	Реалии Hrethgir 01.03.2026 Нет, я не закончил до сих пор симулятор. Эта задача сложнее. Не получилось уйти в плавсостав, но оно и к лучшему, возможно. Точнее получалось - но сварщиком в палубную команду, а это значит, в моём. . .	Ритм жизни kumehtar 27.02.2026 Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .	SDL3 для Web (WebAssembly): Сборка библиотек: SDL3, Box2D, FreeType, SDL3_ttf, SDL3_mixer и SDL3_image из исходников с помощью CMake и Emscripten 8Observer8 27.02.2026 Недавно вышла версия 3. 4. 2 библиотеки SDL3. На странице официальной релиза доступны исходники, готовые DLL (для x86, x64, arm64), а также библиотеки для разработки под Android, MinGW и Visual Studio. . . .
SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .	Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .	Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .

@Rockedit Автор FAQ 1803 / 615 / 37 Регистрация: 22.12.2009 Сообщений: 1,544

	Алгоритм поиска вариантов распределения X ресурсов по N складам, каждый из которых имеет емкость Y 12.04.2011, 12:57. Показов 1833. Ответов 4 Метки нет (Все метки) Всем привет! Решаю следушую задачу. Имеется пользователь с потребностью в X ресурсах. Имеется N складов, на каждом из которых Y ресурсов. Мне нужно получить все варианты, получения пользователем X ресурсов с N складов. Пример Пользователю нужно 6 ед. ресурсов. Есть 2 склада с 6 и 7 ресурсами Варианты 1 склад 2 склад 6 0 5 1 4 2 3 3 2 4 1 5 6 0 Это элементарный пример. На самом деле задача может быть гораздо сложнее, скажем может быть 200 складов, и тогда вариантов очень много. У кого какие идеи как этот процесс можно автоматизировать? Заранее всем спасибо! 0

@XAHOK 273 / 266 / 20 Регистрация: 27.02.2009 Сообщений: 694 Записей в блоге: 7
	12.04.2011, 13:34
	Нечто подобное делал для поиска наиболее оптимального набора действий. Формировал дерево событий, если применительно к твоей задаче, то: Корневые элементы - из склада 1 взято 0 единиц, вложенные узлы из склада 2 взяты 0,1,2...n единиц - из склада 1 взято 1 единиц, вложенные узлы из склада 2 взяты 0,1,2...n-1 единиц - из склада 1 взято 2 единиц, вложенные узлы из склада 2 взяты 0,1,2...n-2 единиц - из склада 1 взято ... Для узлов второго склада аналогично формируется список возможных заборов из склада 3 и т.д. В такой постановке при необходимости легко реализовать многопоточный перебор. Для дополнительной оптимизации можно на этапе формирования каждого слоя находить эквивалентные объемы оставшейся продукции и коллапсировать эти ветки в одну. 1

@Rockedit Автор FAQ 1803 / 615 / 37 Регистрация: 22.12.2009 Сообщений: 1,544
	12.04.2011, 14:25 [ТС]
	Спасибо. идея очень хорошая! Добавлено через 42 минуты Интересно, а как получить все комбинации. к примеру 3 склада с запасами 1 2 2, варианты 0 0 0 0 0 1 0 0 2 0 1 0 0 1 1 0 1 2 0 2 0 0 2 1 0 2 2 1 0 0 1 0 1 1 0 2 1 1 0 1 1 1 1 1 2 1 2 0 1 2 1 1 2 2 а как получить тоже самое для n складов? 0

@XAHOK 273 / 266 / 20 Регистрация: 27.02.2009 Сообщений: 694 Записей в блоге: 7
	12.04.2011, 15:30
	В каждом узле добавлять дополнительные списки по количеству дочерних узлов минус 1. Добавляем в уже существующий значение нулевого узла, а в остальные копируем данные о пути + соответствующий дочерний узел. Получаем нечто наподобие прохождения фронта волны. 1

@nikita2501 0 / 0 / 0 Регистрация: 11.12.2017 Сообщений: 5
	12.12.2017, 19:08
	Можете отправить готовую программу? 0