我想知道以下问题是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?
提前致谢!
可以将此问题的实例减少到Bin Packing(通过使A = B = C = ...)或者到背包(通过仅具有A和B,其中B =总A).Bin Packing和Knapsack都是NP-complete.
| 归档时间： |
|
| 查看次数： |
127 次 |
| 最近记录： |