эффективный алгоритм поиска самых дешевых подмножества

Question

Тема
У нас есть каталог деталей [{id, prodno, qty, price}] и элементов пучков [{id, price, items:[{prodno, qty}]}].
Мы должны найти самые дешевые подмножества (ы) - результат {price, [[{id, qty}]]}, в котором содержатся указанные объекты - запрос [{prodno, qty}].
Пример:

items = [ 
    {id:1, prodno:'A', qty:1, price:1}, 
    {id:2, prodno:'A', qty:5, price:3}, 
    {id:3, prodno:'B', qty:10, price:1} 
] 
bundles = [ 
    {id:4, price:3, items:[ 
    {prodno:'A', qty:2}, 
    {prodno:'B', qty:5} 
    ]} 
] 
query = [ 
    {prodno:'A', qty:5}, 
    {prodno:'B', qty:4} 
] 
result = {price:4, [ 
    [{id:2, qty:1},{id:3, qty:1}] 
]} 

Мы запросили 5xA и 4xB и извлекаться 1 дешевый подмножество (давая 5xA и 10xB).

Answer 1

Это по существу вариант на множестве covering problem.
Если я правильно помню, жадный алгоритм работает очень хорошо для таких проблем, но там могут быть более сложные алгоритмы, которые улучшаются.

Answer 2

Вы можете решить это, найдя кратчайший путь в ориентированном ациклическом графе. Проблема в том, что граф будет иметь лот вершин. Если вы не знаете, как решить такие проблемы с графом, я могу опубликовать некоторые ссылки в комментариях.

Для создания графика вам понадобится столько измерений, сколько значений prodno в запросе, в данном случае 2 (A и B). Каждое измерение будет иметь целочисленный диапазон значений от 0 до qty. Теперь вы можете поместить вершину в каждую позицию, и ваша цель - добраться от [0,0] до [5,4]. Координаты вершин представляют собой суммы prodno.

Чтобы добавить края принять каждый элемент, например {id:1, prodno:'A', qty:1, price:1}, и добавить ребро из каждой вершины [i,j], которая будет идти к вершине [i+1, j] со стоимостью 1. Кромка представляет собой возможность добавить элемент к вашему набору для получения нового набора элементов.

Я не знаю, как вы хотели группы работать, но я правильно понял ваш пример, вы могли бы заплатить 3 использовать группу 4, который добавит 2 * prodno A и 5 * prodno B в свою коллекцию. В этом случае просто добавьте кромку [i,j] в [i+2,j+5] со стоимостью 3.

Еще две детали: каждый край должен помнить, что это id, поэтому, когда вы найдете кратчайший путь, вы можете прочитать, какие элементы или группы использовать. Во-вторых, если край будет идти дальше максимального значения, сделайте так, чтобы оно перешло к максимальному значению: как только вы получили все необходимое количество нулей, вам все равно, сколько у вас будет больше.

Однако это будет довольно медленным для больших входов, поскольку его сложность пропорциональна произведению желаемых количеств всех prodno.