我想知道以下问题是否是NP-完全的,或者是否有特定的算法来解决它:
假设你有一定数额的钱,例如30欧元,硬币和特定价值的钞票(0.01欧元,0.05欧元,5.00欧元.)。所以,问题是:is there a distribution of coins and bills such that every person has the quantity of money that
1)假设我们有一个共同的0-1背包问题。给定一组从1到n的项目,每个项目都有一个权重w_i和一个值v_i,以及一个最大的权重容量W。maximize∑(v_i*x_i), such that ∑(w_i*x_i)≤ W
2)现在假设我们有同样的问题,但是我们需要选择对象,使它们的值和最小,并且它们的权重之和不能小于给定的数目。如果知道第一个问题是NP完全的,那么如何证明第二个问题具有相同的复杂性,换句话说,NP也是完全的?