仅使用两种硬币(x，y)支付账单金额B的最低小费

Question

我有两种硬币（每种类型的硬币不限）。这两种硬币的价值分别为x和y。我必须支付一笔账单B。

作为小费，我需要支付的最低金额是多少。

tip can be any value >=0

目的是尽量减少小费。

我只是在考虑动态编程方法。或者任何更快的方法。请帮忙。

function minTip(x,y,B){
    if(z<=0) return -z;
    return minimum( minTip(x,y,B-x),minTip(x,y,B-y) );
}

有人能帮助DP方法吗。？？

Answer 1

您不需要DP来解决此问题。

首先，请注意，您还可以假设这些硬币是互质的。因为如果它们不是，那么您只能生成gcd的倍数。然后设g＝gcd（x，y），并使用硬币x/g和y/g来解决最小化ceil（B/g）的尖端T的问题。那么原始问题的解决方案是T*g+g*ceil（B/g）-B。

如果x和y是互素，那么不能精确生成的最大数字是xy-x-y。（请参见：https://math.stackexchange.com/questions/66963/largest-integer-that-cant-be-represented-as-a-non-negative-linear-combination-o)

因此，如果B>xy-x-y，那么你保证能够用0小费支付。

否则，你可以通过尝试硬币x的每一个可能组合来找到使用蛮力的解决方案（然后使用最小数量的y来制造至少B）。由于B<xy，这大约是y个不同的值。如果需要，通过交换硬币，这意味着我们可以在O（min（x，y））时间内解决最坏情况下的问题。

将这些整合到一个单独的程序中：

def gcd(x, y):
    x, y = min(x, y), max(x, y)
    while x != 0:
        x, y = y % x, x
    return y
def tip(x, y, B):
    g = gcd(x, y)
    if g != 1:
        nB = (B + g - 1) // g
        T = tip(x // g, y // g, (B + g - 1) // g)
        return T * g + nB * g - B
    if B > x * y - x - y:
        # We're guaranteed to be able to make B exactly.
        return 0
    # Swap the coins if necessary so that x is the larger one.
    x, y = max(x, y), min(x, y)
    T = B
    # Try 0, 1, 2, ... B//x+1 of the x coin.
    # More than this isn't necessary since (B//x+1)*x
    # is already greater than or equal to B.
    for i in xrange(B // x + 2):
        # j is the smallest number of y coins
        # such that ix + jy >= B.
        j = max(0, (B - i * x + y - 1) // y)
        T = min(T, i * x + j * y - B)
    return T
print tip(7, 12, 20)

Answer 2

您可以通过对第一次运算的余数执行具有最大值的模运算和具有较小值的模操作来识别解决方案。您可以循环直到确定最大偏差。工作代码可以在以下垃圾箱中找到。

http://jsbin.com/fivikoh/edit?js，控制台

tipReduce(x,y,z) {
     //find minimum and maximum from x and y
     //find the quotient by dividing z with maxValue
     for(//decrease the quotient till 0) {
      //multiply the quotient with max and the divide the reminder
      //with min value, if the reminder is the zero 'return' it, it is the
      //answer. else store the reminder to find the maximum value of the
      //reminder later. That is used for the tip
        var result =  k * maxValue;
       var reminder =  z - result;
       var reminderDivision = reminder % minValue;
       var divisionWithMinValue = Math.floor(reminder/minValue);
       var calcDifference = z - (result + (divisionWithMinValue *     minValue));
    if(calcDifference > smallestPossible) {
     smallestPossible = calcDifference;
     rememberValues = [k, divisionWithMinValue];
    }
    if(reminderDivision === 0) {
      return [{denom: maxValue, count:k},
            {denom:minValue, count: (reminder/minValue)},
            {tip:0}
           ];
      }
  }

输出函数位于倒数第二行。使用此项可以使用不同的值进行测试。

Answer 3

用DP（任意示例）解决一些硬币兑换问题

使阵列长度B + 1 + min(x, y)

填充这个数组（这里你不需要计数，只有0/1的可能性来求和）

查找索引范围[B.B+min（x，y）]中具有1值的最小条目

Answer 4

混合整数编程方法可能会更快（与DP相比）。

下面是一个示例实现（使用python和cvxpy构建）：

from cvxpy import *
x_y_vals = [3,7]
def solve(vals, amount):
    vars = Int(2)
    constraints = [sum_entries(mul_elemwise(vals, vars)) >= amount,
                   vars >= 0]
    objective = Minimize(sum_entries(mul_elemwise(vals, vars)))
    prob = Problem(objective, constraints)
    prob.solve(solver=CBC)
    print("status:", prob.status)
    print("optimal diff", prob.value)
    print("optimal var", vars.value)
solve(x_y_vals, 300)

呼叫：

solve(x_y_vals, 300)

输出：

('status:', 'optimal')
('optimal diff', 300.0)
('optimal var', matrix([[  2.],
        [ 42.]]))

编辑：正如Paul Hankin所指出的（谢谢！），存在建模错误。我修好了。

备注：CVXPY中的默认MIP解算器仅适用于玩具问题，因此我们需要更好的解算器（否则会遇到数值问题）。这里我们使用cbc，它由cvxpy支持，但需要手动安装（请参阅文档）。