Проблема коллекционера монет

Question

Не могу понять алгоритм слияния пакетов. Кто-нибудь может объяснить алгоритм объединения пакетов пошагово, пожалуйста? Как мы упаковываем и как мы объединяем? Есть ли другой оптимальный алгоритм для решения проблемы коллекционера монет?

Answer 1

Это ответ без кода: я попытаюсь объяснить метод, используя некоторые примеры ситуаций, и надеюсь, что он может быть интуитивно понят из них, когда я обобщу его. Извините, это довольно долго, но если вы прочитаете это методично, это все должно иметь смысл.

Допустим, у коллекционера монет есть два набора монет: набор долларовых монет и набор полдолларовых монет. Однако сборщик монет оценивает каждую монету по-разному, например, на основании даты ее чеканки. Некоторые очень редки и поэтому более ценны.

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

Допустим, у него есть 7-долларовые монеты и 5 полдолларовых монет, и он хочет купить что-то на 4 доллара. Упрощенным решением было бы взять только его долларовые монеты и ранжировать их по значению, выбрать 4 наименее ценных и передать их, положив в карман оставшиеся 3 долларовые монеты, которые являются наиболее ценными.

Но затем он понимает, что, если он возьмет две половинки доллара и "упакует" их вместе, он может рассматривать пакет как новую монетку размером в доллар. Клерку у стойки стоит доллар, а для коллекционера - совокупная стоимость двух отдельных полдолларов, которые он использовал.

Тогда лучшая стратегия - посмотреть на его полдоллара, взять самые дешевые два, собрать их вместе как новую долларовую «монету» и добавить («объединить») в свой набор долларов. Так что теперь у него 8 (7 + 1) долларовых монет / пакетов и 3 (5-2) полдоллара.

Этот шаг можно повторить еще раз, и теперь у него 9 монет / пакетов размером с доллар и 1 оставшийся полдоллара, который не может быть упакован ни с чем другим. Поскольку это его самый ценный полдоллара, он понимает, что не должен его использовать, и кладет его снова в карман, эффективно устраняя его из проблемы.

Теперь у него просто есть набор монет / пакетов размером с 9 долларов. Он сортирует их по значению, выбирает 4 наименее ценных и передает их клерку, кладя в карман оставшиеся (наиболее ценные) монеты.

Чтобы немного обобщить: представьте, у него также есть несколько четвертей с ним. Перед упаковкой полдолларовых монет он должен сначала упаковать кварталы в полдолларовые пакеты (по очереди выбирая самые дешевые пары, выбрасывая наиболее ценный остаток, если он есть), а затем объединить их в набор полдолларовых монет. .

Гипотетически возможны меньшие номиналы: 1/8 доллара, 1/16 доллара и т. Д. Если они являются отрицательными степенями двух, стратегию можно обобщать: сортировать монеты наименьшего достоинства, упаковать их, объединить пакеты в набор следующего наименьшего номинала и продолжайте, пока у вас не будут только монеты / пакеты размером с доллар.

(Есть еще один случай, который стоит рассмотреть: если запрашиваемая цена не является круглой цифрой в долларах, например, 7 1/4 доллара. В этом случае, перед упаковкой монет / пакетов четвертого размера, вы сначала выбираете самую дешевую, передать его и вычесть из запрашиваемой цены, затем упаковать оставшиеся. Это также может быть обобщено: всякий раз, когда цена требует определенной деноминации (то есть она является нечетным кратным этой деноминации); при упаковке этого наименования вы сначала удаляете самый дешевый, вычитая его из цены. К тому времени, когда вы доберетесь до долларовой стадии, цена будет равна целому числу долларов.)

Answer 2

Я считаю, что аналогия с монетами бесполезна.Вы тоже можете.Для меня более интуитивно понятно рассмотреть набор стержней различной длины с степенью двойки: 1/4, 1/2, 1, 2, 4, 8, .... Каждый стержень имеет свою цену.Вам нужно потратить наименьшее количество денег на удилища и все же пройти некоторое точное расстояние X.

С любой комбинацией этих удилищ вы можете только / точно / размахить расстояние, которое является диадическим, то есть ", которое имеет только факторыдва в его знаменателе ", т.е. имеет завершающее двоичное представление после точки.Вы не можете охватить 1/5 или 4 3/7, потому что никакое конечное число стержней точно не соответствует таким расстояниям, всегда будет немного больше.

Итак, если вы действительно покрываете диадическую букву X, чтостержни ты используешь?Подумайте о наименьшей двоичной дроби, используемой на вашем расстоянии X. Если X 13/128, то это 1/128.Это уровень точности, который вам нужен.

а.Если все ваши удилища больше 1/128, значит, вы набиты.Ни один из ваших удилищ не достаточно хорош, чтобы продержаться 1/128.Неудача.

б.Если 1/128 - самый маленький вид вашей удочки, вам придется использовать хотя бы одну из них.Там нет выбора, чтобы пройти это дополнительное крошечное расстояние: вы собираетесь использовать один.Так что с таким же успехом можно купить самый дешевый стержень 1/128 сейчас.Затем вы можете решить оставшуюся чуть меньшую задачу (13 1/64) с оставшимися стержнями.

c.Если ваш самый маленький жезл меньше 1/128 (скажем, 1/512), то возможно, что вы будете использовать их, но только четное количество.Если вы используете нечетное число, у вас останется небольшое количество (здесь 1/512), и что бы вы ни делали с более крупными стержнями, вы не сможете избавиться от этого лишнего куска, и вы набиты.Таким образом, вы либо не будете использовать ни один из них или четное число.Если в итоге вы используете два, вы в конечном итоге будете использовать самые дешевые два.Если вы в конечном итоге используете четыре, вы в конечном итоге будете использовать самую дешевую четверку и т. Д.

Таким образом, вы будете использовать их в парах.Если вы возьмете самые дешевые два - скажем, они стоят 5 пенсов и 7 пенсов - тогда, если вы используете их, то вы будете использовать их эффективно, как если бы они были одной частью 1/256, стоимостью 12 пенсов.Так что возьмите их из колоды 1/512 и рассмотрите их, как будто 12p 1/256 фигуры вместе со всеми остальными 1/256 фигурами.Оставшаяся третья часть 1/512, самая дорогая, бесполезна, она не будет использоваться по вышеуказанной причине, она слишком хороша и оставит эту крошечную долю.

Теперь мы закончилис кучей 1/512, теперь вы можете рассмотреть груду 1/256, которая теперь является самой маленькой и, возможно, имеет в ней надлежащую 1/256 (скажем, стоимость 8р), а также наш «пакет» из двух 1/512 (стоит скажем 12р).Затем вы можете упаковать их в пару, используя приведенные выше аргументы.Его стоимость составляет 20 пенсов и эквивалентна 1/128.

Вы еще не взяли на себя обязательство использовать ни один из этих пакетов, вы просто знаете, что если вы это сделаете, вы будете использовать весь пакет.И вы продолжаете увеличивать размеры, уменьшая проблему каждый раз, либо уменьшая общее количество кусков по упаковке, либо уменьшая цель.

Таким образом, в конечном итоге вы достигнете своей цели или докажетечто вы не можете.

Самое главное - помнить, что когда вы собираете пакет, вы не берете на себя обязательство использовать его, вы просто говорите / если / вы делаете,тогда вы будете использовать стержни внутри как единое целое.

Answer 3

Это не поддается очень короткому объяснению; Вы читали страницу Википедии?