algorithm - 代币分配练习——它是 NP 完全的吗？

Question

我想知道以下问题是否是 NP 完全问题，或者是否有解决它的特定算法:

假设您有一定数量的钱，例如 30 欧元，有特定值(value)的硬币和纸币(0.01 欧元、0.05 欧元、5.00 欧元...)。

我们拥有的硬币和钞票的数量是给定的，您必须将其分配给A、B、C、等等

您希望A 有一定数量的钱(例如 10 欧元)，B 有不同或相等的数量，等等。

“需要”的钱的总和并不大于我们拥有的钱。

那么，问题是:是否存在这样一种硬币和钞票的分配方式，使得每个人都拥有属于他的货币数量？

提前致谢!

Answer 1

可以将此问题的实例简化为 Bin Packing(通过使 A=B=C=...)或 Knapsack(通过只有 A 和 B，且 B=total-A)。众所周知，Bin Packing 和 Knapsack 都是 NP 完全的。