Поиск наиболее оптимального способа заполнения QList блоками разной длины для приближения к заданному количеству
Имеется QList<Container *> Класс Container в свою очередь имеет QList<Item *> в котором может быть произвольное количество Item не менее одного. Имеется QList<Item *> resList для хранения результата.
При вводе пользователем числа необходимо копировать указатели Item * из контейнеров соблюдая следующие условия:
- Добавлять можно только все Item из Container
- Итоговое количество Item в resList должно быть как можно ближе к числу, введенному пользователем, но не меньше.
- Можно удалять ранее добавленные Item из resList, но удалять можно только все Item которые входят в общий Container
- Если число, которое ввел пользователь меньше, чем количество Item в resList, то можно и удалять и добавлять по тем же правилам с тем же условием.
Задача найти наиболее оптимальный алгоритм, чтобы как можно меньше перебирать списки и как можно меньше удалять и добавлять Item в/из resList
upd: Попробую более детально расписать суть задачи (на абстрактном примере), так как на основе предоставленных ранее данных, вероятно, сложно дать точный ответ.
Имеется некий склад предметов одного типа. Предметы могут храниться в контейнерах разного размера от 1 до N, либо лежать без контейнера поштучно. На склад приходит запрос выдать x количество предметов. Склад на основе имеющихся в наличии предметов должен постараться выдать точно x либо больше, но не меньше. При этом в приоритете выдавать сначала предметы контейнерами и только потом, если подходящего контейнера нет выдавать поштучно. При этом если от того же пользователя приходит повторный запрос на новое количество y, склад должен проанализировать:
- Сколько ранее выдано предметов и какой конфигурацией комплектов/россыпью
- Сколько осталось в наличии и в какой конфигурации
- На основе этих данных либо выдать еще, если запрошено больше, либо забрать часть, если запрошено меньше, либо забрать часть и выдать что-то в другой конфигурации, чтобы соблюсти условие выдать точно y либо больше, совершив как можно меньше действий возврата-выдачи.
Примеры: Допустим имеем контейнеры с количеством предметов [4,4,3,2] и еще 1 россыпью. Пользователь запросил 6, значит нужно выдать первый и четвертый комплект.
Затем пользователь запросил вместо 6 7. Значит нужно четвертый забрать, а взамен выдать третий.
Затем пользователь запросил 9, значит выдать еще четвертый
Надеюсь теперь я более детально описал суть задачи.
Ответы (1 шт):
Задача при умеренных значениях сумм решается динамическим программированием.
Вначале заводим массив А длиной в нужную сумму +1, заполняем большим числом X, A[0]=0.
Затем для каждого значения контейнера v проходим по массиву сверху вниз. A[i]= min(A[i-v]+1, A[i]) - это означает, что сумму i можно составить из v и i-v, выбрав минимальное количество слагаемых из текущего и новой суммы.
После работы алгоритма ячейка массива A[neededsum] содержит количество (минимальное) контейнеров для набора данной суммы. Для учёта перебора массив нужно удлинить и проверять ячейки от neededsum вверх.
Похожим образом работаем при обновлении нужной суммы, только теперь отложенные ранее контейнеры используем со знаком минус, а в качестве целевой суммы берём разность между прошлой и новой. При этом суммы могут быть отрицательными, индексы массива неудобны, можно взять словарь.
Если алгоритм заработает, останется небольшая модификация - сохранять при выборе минимума информацию о том, какие именно контейнеры использованы на данную сумму.