硬幣分配練習 - 是NP完成嗎？

Question

我想知道以下問題是NP-Complete還是有特定算法可以解決這個問題：

想象一下，您有一定的金錢，例如30歐元，硬幣和特定值的帳單（ 0.01€，0.05€，5.00€...）。

我們已經給出了硬幣和鈔票的數量，你必須把它分配當中有些人一個，乙，Ç等

你想一個有一定數量的金錢（例如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包裝和揹包都是NP-complete。