Занятие по распределению монет - это NP-Complete?

Question

Я хочу знать, если следующая проблема NP-полная или если есть конкретный алгоритм, который решает, что:

Представьте у вас есть определенное количество денег, 30 евро, например, в монетах и ​​векселей конкретных значений (0,01 €, 0,05 €, 5,00 € ...).

Количество монет и банкнот мы дается, и вы должны распространять среди некоторых людей , B, C и т.д.

Вы хотите иметь определенную сумму денег (например, 10 €), B - другую или равную сумму и т. д.

Сумма «требуемых» денег не больше, чем у нас.

Итак, вопрос: is there a distribution of coins and bills such that every person has the quantity of money that belongs to him?

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

Answer 1

Можно уменьшить экземпляры этой проблемы до Bin Packing (с помощью A = B = C = ...) или с помощью Knapsack (имея только A и B, с B = total-A). Как Bin Packing, так и Knapsack, как известно, NP-полные.