javascript - 将一个数字转换为另外两个数字的总和，使差异最小

Question

In Mars, there are only two denominations of currency ,x and y. AMarsian goes to a bar and the bill is "z". Using x and y he has to paythe bill. But the bar doesn't tender change, any extra money will betaken as tips.

So write a function in JavaScript that helps the marsian to reduce thetips.

The function takes in x, y, z and returns the amount of tip he has topay.

Example 1

Input: 2, 5, 109

Output: 0

Explanation: 21 coins of 5, and 2 coins of 2

Example 2

Input: 5, 7, 43

Output: 0

Explanation: 4 coins of 7, and 3 coins of 5

Example 3

Input: 15, 19, 33

Output: 1

Explanation: 1 coin of 15 and 1 coin of 19

解决方案: 我认为这是一级 DP 问题，类似于子集和。就像为更大的数字找到最佳小费一样，了解以下所有数字的最佳小费会有所帮助。

const coinA = 2
const coinB = 5
const sum = 13

var arr = [];
arr[0] =0;
console.log(getMyTip(coinA, coinB, sum));
function getMyTip(){
    for(var i=1; i<= sum; i++){
        var minA, minB;
        if( i < coinA){
          minA = coinA - i;
        }else{
          minA = arr[i - coinA];
        }
        if( i < coinB){
         minB = coinB - i;
        }else{
         minB = arr [i - coinB]
        }
        arr[i] = Math.min(minA, minB);
    }
    return arr[sum];

}

Jsfiddle:https://jsfiddle.net/7c4sbe46/

但我不确定为什么它没有被接受。如果我遗漏了此处的逻辑，请告诉我。

Answer 1

与diophantine equations更相关，即 a.x+b.y=z 有解决方案吗？如果 z 是 x 和 y 的最大公约数(称为 gcd)的倍数，则答案是肯定的。如果不是，您的小费将是 1. 可被 gcd 整除的较小数字和大于 z 之间的差值和 2.z。一旦知道了 tip 的值，您甚至可以通过将 z 的值稍微修改为 (z+tip) 来轻松知道您需要的 x 和 y 的数量。