自从昨天站在超市的销售点,再次尝试启发式地找到我的硬币的最佳分区,同时试图忽略我身后不耐烦和紧张的队列,我一直在思考潜在的算法问题:
给定一个价值为 v 1 ,...,v n的硬币系统,有限数量的硬币 a 1 ,...,a n以及我们需要支付的金额 s。我们正在寻找一种算法来计算分区 x 1 ,...,x n (with 0<=x i <=a i ) with x 1 *v 1 +x 2 *v 2 +...+x n *v n >= s 使得总和 x 1 +...+x n - R(r) 最大化,其中 r 是变化,即 r = x 1 *v 1 +x 2 *v 2 +。 ..+xn *v n - s 和 R(r) 是从收银员返回的硬币数量。我们假设收银员拥有无限数量的所有硬币,并且总是返还最少数量的硬币(例如使用 SCHOENING 等人解释的贪婪算法)。我们还需要确保没有换钱,所以最好的解决方案不是简单地给所有的钱(因为在这种情况下解决方案总是最优的)。
感谢您的创意输入!