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

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

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

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

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

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

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

11
задан luca 27 February 2011 в 14:07
поделиться