algorithm - 硬币分配练习 - 是 NP-Complete 吗？

Question

我想知道以下问题是否是 NP-Complete 或者是否有解决它的特定算法：

想象一下，您有一定数量的钱，例如 30 欧元，硬币和特定价值的钞票（0.01 欧元、0.05 欧元、5.00 欧元......）。

我们已经给出了硬币和纸币的数量，您必须将其分配给A、B、C等人。

您希望A有一定数量的钱（例如 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

可以将此问题的实例减少到装箱（通过 A=B=C=...）或背包（通过只有 A 和 B，B=total-A）。Bin Packing 和 Knapsack 都被认为是 NP 完全的。