Динамический подход T-SQL для комбинаторики / ранца

Я предполагаю, что мой вопрос имеет отношение к варианту проблемы ранца, но я не могу действительно найти решение для этого:

Допустим, вы находитесь в хозяйственном магазине и вам нужно купить 21 болт. Они предлагают их только в сумках:

Сумка X - 16 винтов - 1,56 $ за винт - 25 $ ВсегоСумка Y - 8 винтов - 2,25 $ за винт - 18 $ ВсегоСумка Z - 4 винта - 1,75 $ за винт - 7 $ Итого

Теперь вам нужно выяснить, какие сумки вы должны купить, чтобы получить 21 винт (или больше!) По самой низкой цене.

Итак, я получил таблицу со всеми сумками и переменную для определения необходимого количества. В результате мне нужна таблица с именем сумки и необходимой суммой.

К сожалению, sqlfiddle не работает .. Но, по крайней мере, вот пример данных:

declare @bags table (id int, qty int, price decimal(19,4))
insert into @bags values
 (10, 16, 25.00)
,(20, 8, 18.00)
,(30, 4, 7.00)

declare @ReqQty int = 21

Я очень ценю вашу помощь! Надеюсь, мы сможем решить эту проблему, так как мне нужно настроить ERP-систему нашей компании с помощью этой важной функции.

Заранее спасибо!

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

Так что, кажется, мне лучше использовать жадный алгоритм, а не изобретать колесо? ;)

Ответы на вопрос(2)

Ваш ответ на вопрос