Алгоритм «переноса воды из набора бутылок в другой» (образно говоря) - PullRequest
Новая
       17

Алгоритм «переноса воды из набора бутылок в другой» (образно говоря)

11 голосов
/ 27 февраля 2011

Хорошо, у меня проблема.У меня есть набор «А» бутылок разных размеров, наполненных водой.Затем у меня есть другой набор бутылок разных размеров "B", все пустые.

Я хочу перевести воду из A в B, зная, что общая вместимость каждого набора одинакова.(то есть: набор A содержит столько же воды, сколько набор B).

Это само по себе тривиально, просто возьмите первую бутылку в B, налейте ее в первую в A, пока она не заполнится.Затем, если в бутылке из B все еще есть вода, продолжайте вторую бутылку в A и т. Д.

Однако я хочу минимизировать общее количество наливов (действие выливания из бутылки в другую).каждое действие считается равным 1, независимо от того, сколько воды оно включает)

Я бы хотел найти жадный алгоритм для этого или, если это невозможно, по крайней мере эффективный.Однако эффективность является вторичной по отношению к правильности алгоритма (я не хочу неоптимального решения).

Конечно, эта проблема - всего лишь метафора реальной проблемы в компьютерной программе для управления личными расходами.

Ответы [ 3 ]

8 голосов
/ 27 февраля 2011

Плохая новость: эта проблема является NP-трудной из-за сокращения от подмножества суммы. Для заданных чисел x 1 ,…, x n , S целью суммы подмножества является определение того, является ли некоторое подмножество суммы x i s S. Мы производим A-бутылки емкостью x 1 ,…, x n и B-бутылки емкостью S и (x 1 +… + x n - S) и определить, достаточно ли n заливок.

Хорошая новость: любая жадная стратегия (то есть, выбирайте любую непустую A, выбирайте любую незаполненную B, наливайте до тех пор, пока мы не остановимся) - это 2-аппроксимация (т. Е. Используется не более чем в два раза больше, чем оптимально). Оптимальное решение использует как минимум max (| A |, | B |) заливки, а жадные - не более | A | + | B |, так как каждый раз, когда жадный наливает, либо A сливается, либо B заполняется и не нуждается в разливе или повторении.

Может существовать схема аппроксимации ((1 + ε) -аппроксимация для любого ε> 0). Теперь я думаю, что более вероятно, что есть результат неприемлемости - обычные приемы для получения схем аппроксимации не похоже здесь.

Вот некоторые идеи, которые могут привести к практическому точному алгоритму.

Если дано решение, нарисуйте двудольный граф с левыми вершинами A и правыми вершинами B и (ненаправленным) ребром от a до b тогда и только тогда, когда a выливается в b , Если решение является оптимальным, я утверждаю, что циклов нет - в противном случае мы могли бы устранить наименьшую заливку в цикле и заменить потерянный объем, идущий вокруг цикла. Например, если у меня льется 

a1 -> b1: 1
a1 -> b2: 2
a2 -> b1: 3
a2 -> b3: 4
a3 -> b2: 5
a3 -> b3: 6

тогда я могу устранить на a1 -> b1 лей так: 

a2 -> b1: 4 (+1)
a2 -> b3: 3 (-1)
a3 -> b3: 7 (+1)
a3 -> b2: 4 (-1)
a1 -> b2: 3 (+1)

Теперь, поскольку на графике нет цикла, мы можем посчитать количество ребер (заливок) как |A| + |B| - #(connected components). Единственная переменная здесь - это количество подключенных компонентов, которое мы хотим максимизировать.

Я утверждаю, что жадный алгоритм формирует графики без цикла. Если бы мы знали, каковы были связанные компоненты оптимального решения, мы могли бы использовать жадный алгоритм для каждого и получить оптимальное решение.

Один из способов решения этой подзадачи состоит в том, чтобы использовать динамическое программирование для перечисления всех пар подмножеств X из A и Y из B, таких что sum (X) == sum (Y), а затем передать их в точный алгоритм покрытия. Оба шага, конечно, экспоненциальные, но они могут хорошо работать с реальными данными.

3 голосов
/ 27 февраля 2011

Вот мой дубль:

  1. Определите бутылки одинакового размера в обоих наборах. Это означает, что эти бутылки одинакового размера будут наливаться один на один.
  2. Сортировка оставшихся бутылок в A в порядке убывания по вместимости и сортировка оставшихся бутылок в B в порядке возрастания. Вычислите количество заливок, необходимое для заливки отсортированного списка от A до B.

Обновление: После каждой заливки на шаге 2 повторяйте шаг 1. (Шаг оптимизации, предложенный Стивом Джессопом ). Промойте и повторяйте, пока вся вода не будет передана.

0 голосов
/ 27 февраля 2011

я думаю, что это дает минимальное количество разливов: 

import bisect

def pours(A, B):
    assert sum(A) == sum(B)
    count = 0
    A.sort()
    B.sort()
    while A and B:
        i = A.pop()
        j = B.pop()
        if i == j:
            count += 1
        elif i > j:
            bisect.insort(A, i-j)
            count += 1
        elif i < j:
            bisect.insort(B, j-i)
            count += 1
    return count

A=[5,4]
B=[4,4,1]
print pours(A,B)
# gives 3

A=[5,3,2,1] 
B=[4,3,2,1,1]
print pours(A,B)
# gives 5

на английском это гласит:

  • утверждают, что оба списка имеют одинаковую сумму (я думаю, что алгоритм все равно будет работать, если sum(A) > sum(B) или sum(A) < sum(B) истинно)
  • возьмите два списка А и В, отсортируйте оба их

пока A не пусто и B не пусто:

  • взять I (самое большое) из A и J (самое большое) из B
  • если я равняюсь j, налить i в j и считать 1 на
  • если i больше j, залить i в j, поместить остаток i-j обратно в A (используя сортировку вставкой), считать 1 за
  • если я меньше j, залить i в j, поместить остаток j-i обратно в B (используя сортировку вставкой), считать 1 за
...