2種類の硬貨（x、y）のみでB金額を支払う最小チップ

Question

私は2種類の硬貨（各種類の無制限硬貨）を持っています。 これらの2つのコインの値は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

Mixed-Integer Programmingアプローチは、おそらくはるかに高速（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.]])) 

はEDIT：で指摘したようにポールハンキン（感謝！）、モデリングエラーがありました。それを私が直した。

備考： CVXPYのデフォルトMIPソルバーのみおもちゃ-問題に取り組んでいるので、私たちはより良い解法を必要とする（または私たちは、数値のトラブルに実行します）。ここでは、cvxpyでサポートされているcbcを使用しますが、手動でインストールする必要があります（ドキュメントを参照）。

Answer 2

（ここではあなたは、合計を作るためにのみ0/1可能性がカウントを必要としない）配列長 B + 1 + min(x, y)

は、この配列を記入してくださいDPといくつかのコイン変動問題の解決（arbitrary example）

を取ります

インデックス範囲[B..B + min（x、y）]に1の値を持つ最小エントリを探します。

Answer 3

これを解決するためにDPは必要ありません。

まず、コインがコモンであると仮定することもできます。なぜなら、そうでなければ、gcdの倍数しか生成できないからです。次にg = gcd（x、y）とし、コインx/gとy/gを使ってceil（B/g）の先端Tを最小化する問題を解く。そして元の問題の解はT * g + g * ceil（B/g） - Bです。

xとy は互いに素である場合、あなたはがを正確に生成することはできません最大数は、xyです - XY。 （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 4

。最大偏差を特定するまでループバックすることができます。 作業コードは、次のビンにあります。

http://jsbin.com/fivikoh/edit?js,console

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} 
      ]; 
     } 
    } 

出力機能は、最後が、1つのラインです。これを使用して異なる値でテストします。