两个表的组合以填充距离D算法

Question

假定两种类型的表，X越短，Y越长。对齐两种类型的表以填充距离D。找到最佳组合以保持剩余的空距离尽可能小。第一要务是最小化空车距离第二优先级是尽量减少已使用表的数量

例如输入：X = 3，Y = 5，D = 24最佳组合为：TX = 3，TY = 3，RD = 0基于while循环和if-else语句的解决方案

 R=24
 X=3
 Y=5
 while(R>X):
   if R%Y==0:
      TY=R/Y
      R=0
   else if RD % X == 0:
      TX=R%X
      R=0

但不是最佳解决方案

Answer 1

这很难理解，您实际上是在谈论要吃的桌子，而X和Y是桌子的长度，而D是您想要通过组合长度为X和Y的桌子获得的所需长度。

这里是一个解决方案，假设您必须找到最小的长度> = D，否则有些人没有座位（如果有几种方法可以解决此问题，则该解决方案还会尝试使用尽可能多的长桌Y达到最佳值，因此也减少了所需的表数），

<< [comments显示要更改以获取最大数量的表<= D：

function solve(x, y, d) {
    let tX = 0, tY = Math.ceil(d / y), tD = tY * y, // floor
        bestX = 0, bestY = tY, bestD = tD, seen = []
    while (tD != d && !seen[tD]) {
        seen[tD] = true
        tD = ++tX * x
        if (tD >= d) // if (tD > d) break
            return tD < bestD ? [tX, 0, tD - d] : [bestX, bestY, bestD - d]
        tY = Math.ceil((d - tD) / y) // floor
        tD += tY * y
        if (tD < bestD) { // tD > bestD
            bestX = tX
            bestY = tY
            bestD = tD
        }
    }
    return [bestX, bestY, bestD - d] // d - bestD
}

console.log(solve(3, 5, 24))
console.log(solve(64, 80, 999999981))