只有两种硬币（x，y）才能支付账单金额B的最低费用 [英] Minimum tip to be paid for bill amount B with two kind of coins (x,y) only

问题描述

我有两种硬币（每种类型的无限硬币）。
这两个硬币的值是 x和y 。
我必须支付一笔金额 B 。

我需要什么最低金额支付提示。

 提示可以是任何值> = 0 
  

目标是尽量减少提示。

$ b $我刚刚在考虑动态编程方法。任何更快的方法。
请帮助。

  function minTip（x，y，B）{
 if（z < 0）return -z; 
返回最小值（minTip（x，y，B-x），minTip（x，y，B-y））; 
} 
  

可以帮助DP方法。

解决方案

您不需要DP来解决这个问题。 b
$ b

首先，请注意，你也可以假设硬币是互惠的。因为如果不是，那么你只能生成gcd的倍数。然后让g = gcd（x，y），并解决使用硬币x / g和y / g最小化细胞末端T（B / g）的问题。那么原始问题的解决方案是T * g + g * ceil（B / g）-B。

如果x和y 是互惠原子，那么您不能生成的最大数字就是xy - x - y。 （见： http ：//math.stackexchange.com/questions/66963/largest-integer-that-c​​ant-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） （x，y）
而x！= 0：
x，y = y％x，x 
 return y 
 
 def tip（x，y，B） ：
g = gcd（x，y）
如果g！= 1：
 nB =（B + g  -  1）// g 
 T = tip ，y // g，（B + g  -  1）// g）
返回T * g + nB * g  -  B 
如果B> x * y  -  x  -  y：
＃我们保证能够使B完全正确。 
返回0 
＃如果需要，交换硬币，以便x是较大的。 
x，y = max（x，y），min（x，y）
 T = B 
＃尝试0，1，2，... B // x + 1 x硬币（b // x + 1）* x 
＃已经大于或等于B. 
 for x in xrange（B // x + 2）：
＃j是y硬币的最小数量
＃，使ix + jy> = B. 
j = max（0，（B  -  i * x + y  - 1）// y）
 T = min（T，i * x + j * y-B）
 return T 
 
打印提示（7，12，20）
  

I have two kind of coins (unlimited coins of each type). The values of these two coins are x and y. I have to pay a bill of amount B.

What minimum amount i will need to pay as tip.

tip can be any value >=0

The objective is to minimize the tip.

I just was thinking about the Dynamic programming approach.Or any Faster method. Please help.

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

Can any one help with the DP approach.??

解决方案

You don't need DP to solve this.

First, note that you may as well assume the coins are coprime. Because if they're not then you can only generate multiples of the gcd. Then let g = gcd(x, y) and solve the problem of minimizing the tip T of ceil(B / g) using coins x/g and y/g. Then the solution to the original problem is T*g + g * ceil(B / g) - B.

If x and y are coprime, then the largest number you can't generate exactly is xy - x - y. (See: http://math.stackexchange.com/questions/66963/largest-integer-that-cant-be-represented-as-a-non-negative-linear-combination-o)

So if B > xy - x - y, then you're guaranteed to be able to pay exactly with 0 tip.

Otherwise, you can find the solution using brute force by trying every possible combination of coin x (and then using the smallest number of y to make at least B). Since B < xy, that's approximately y different values. By swapping the coins if necessary, that means we can solve the problem in the worst case in O(min(x, y)) time.

Putting that together into a single program:

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)

这篇关于只有两种硬币（x，y）才能支付账单金额B的最低费用的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！