Сочетание двух таблиц для заполнения алгоритма расстояния D

Question

Предположим, что есть два типа таблиц: короче X, а длиннее Y. Комбинация двух типов таблиц выравнивается, чтобы заполнить расстояние D. Найдите оптимальную комбинацию, чтобы оставшееся пустое расстояние было как можно меньше. первый приоритет - минимизировать пустое расстояние, второй приоритет - минимизировать количество используемых таблиц

ex Вход: X = 3, Y = 5, D = 24 Оптимальная комбинация: TX = 3, TY = 3, RD = 0 мое решение, основанное на операторах while l oop и 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

Возможно, есть решение O(1).
(Этот ответ предполагает, что вопрос означает окончательную длину <= D </strong>, а не наоборот.)

---

Logi c

Шаги:

* First, calculate initial max Y as b, then min X as a, and get a initial gap.
* if (gap > 0) && (Y % X >0), then:
    * figure out a group of X to replace a single Y, to reduce gap by Z,
    * reduce the gap by exhange Xs & Y,
    * re-calculate: a, b, gap,
* return new int[] {a, b, gap};

Сложность :

• Время : O(1)
• Пробел: O(1)

---

Код (Java)

• CombineTwoTables. java

public class CombineTwoTables {
    public static int[] findByExchange(int X, int Y, int D) {
        int b = D / Y; // count of Y,
        int gap = D - b * Y; // gap left,

        int a = gap / X; // count of X,
        gap = gap - a * X;

        if (gap > 0) {
            int Z = Y % X;
            if (Z > 0) { // when Z == 0, any further step is useless,
                Z = X - Z;
                int exchanges = gap / Z;
                if (exchanges > 0) {
                    int xs = Y / X + 1; // count of x in each exchange,

                    a = a + exchanges * xs;
                    b = b - exchanges;
                    gap = gap - exchanges * Z;
                }
            }
        }

        return new int[]{a, b, gap};
    }
}

• CombineTwoTablesTest. java
  (контрольный пример, через TestNG)

import org.testng.Assert;
import org.testng.annotations.Test;

import java.util.Arrays;

public class CombineTwoTablesTest {
    @Test
    public void testFindByExchange() {
        runOnce(3, 5, 24, new int[]{3, 3, 0});

        runOnce(64, 80, 999999981, new int[]{2, 12499998, 13});

        runOnce(6, 10, 1026, new int[]{1, 102, 0});
        runOnce(6, 10, 1025, new int[]{4, 100, 1});
        runOnce(6, 10, 1024, new int[]{4, 100, 0});
        runOnce(6, 10, 1023, new int[]{2, 101, 1});
        runOnce(6, 10, 1022, new int[]{2, 101, 0});
        runOnce(6, 10, 1021, new int[]{0, 102, 1});
    }

    private void runOnce(int X, int Y, int D, int[] expected) {
        int[] result = CombineTwoTables.findByExchange(X, Y, D);
        System.out.printf("input: X = %d, Y = %d, D = %d,\texpected: %s,\tresult: %s\n", X, Y, D, Arrays.toString(expected), Arrays.toString(result));
        Assert.assertEquals(result, expected);
    }
}

Весь тестовый набор будет пройден , с выводом:

input: X = 3, Y = 5, D = 24,    expected: [3, 3, 0],    result: [3, 3, 0]
input: X = 64, Y = 80, D = 999999981,   expected: [2, 12499998, 13],    result: [2, 12499998, 13]
input: X = 6, Y = 10, D = 1026, expected: [1, 102, 0],  result: [1, 102, 0]
input: X = 6, Y = 10, D = 1025, expected: [4, 100, 1],  result: [4, 100, 1]
input: X = 6, Y = 10, D = 1024, expected: [4, 100, 0],  result: [4, 100, 0]
input: X = 6, Y = 10, D = 1023, expected: [2, 101, 1],  result: [2, 101, 1]
input: X = 6, Y = 10, D = 1022, expected: [2, 101, 0],  result: [2, 101, 0]
input: X = 6, Y = 10, D = 1021, expected: [0, 102, 1],  result: [0, 102, 1]

---

Советы

• Чтобы сделать вещи более понятными, операторов, таких как +=, -=, избегают, и вместо них используют =.
• Если вы предполагаете target length >= D, то, вероятно, существует аналогичное решение, хотя я на самом деле не думал об этом.

Answer 2

Это было трудно понять, вы на самом деле говорите о столах для еды, и X и Y - это длина таблиц, а D - это желаемая длина, которую вы хотите получить, комбинируя таблицы длин X и Y.

Вот решение, предполагающее, что вы должны найти наименьшую длину> = D, в противном случае у некоторых людей нет места (это решение также пытается занять как можно больше более длинных столов Y, если их несколько). способы достижения оптимального значения и, следовательно, также минимизирует количество необходимых таблиц), комментарии показывают, что необходимо изменить, чтобы получить наибольшее число <= D </em>:

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))

Это на самом деле очень просто: вы просто увеличиваете tX шаг за шагом, вычисляете лучший tY для этого tX и отслеживаете лучшее решение. Чтобы не повторять одно и то же снова и снова, мы отслеживаем видимую длину таблицы (это будет цикл, и если вы снова столкнетесь с одним и тем же значением, вы знаете, что вы уже видели оптимальное значение). Это полезно для входов, таких как X = 64, Y = 80 и D = 999999981 (обратите внимание, что это странно и никогда не может быть достигнуто). Он находит решение TX = 1, TY = 12499999 и RD = 3 почти сразу.