Алгоритм объединения таблицы двух размеров для заполнения заданного пространства - PullRequest
Новая
       9

Алгоритм объединения таблицы двух размеров для заполнения заданного пространства

0 голосов
/ 23 апреля 2020

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

Используя как можно меньше таблиц, найдите оптимальную комбинацию, чтобы оставшееся пустое расстояние было как можно меньше. [примечание: первый приоритет - минимизировать пустое расстояние, а второй - минимизировать количество используемых таблиц]

Примеры: ввод: X = 3, Y = 5, D = 24

Оптимальная комбинация: TX = 3, TY = 3, RD = 0

Это означает: три таблицы размера X (TX), три таблицы размера Y (TY) и оставшееся расстояние ( RD) равно 0.

3 * 3 + 3 * 5 = 24

Таким образом, пустое расстояние = 24 - 24 = 0

Ввод: X = 3, Y = 9 , D = 29

Выход: TX = 0, TY = 3, RD = 2

Это означает: нулевые таблицы размера X (TX), три таблицы размера Y (TY), и оставшееся расстояние (RD) составляет 2.

0 * 3 + 3 * 9 = 27

То есть пустое расстояние = 29 - 27 = 2 

  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

Вот что Я go пока, но я думаю, что должны быть более точные и оптимальные решения.

...