Как получить нужное число, который получается в результате сложения чисел из указанного массива?

Question

[AigizK]

Пусть у нас есть массив чисел. Задается число и надо представить это число как сумму чисел из этого массива.
Например:
А=[2,3,5,5,7]
Если B=10 то один из способов 2+3+5, а можно еще 5+5
Если В=6, то нет решения

Ограничения:
1. Числа в массиве могут повторяться
2. Одно число из массива нельзя использовать более 1 раза. Т.е. если надо получить 15, то не могу получить так 5+5+5,т.к. пятерок всего два.

Дополнение:
Я знаю, какие числа могут встречаться в массиве. Это: 1, 2, 5, 10, 50, 100, 500, 1000, 5000. Других быть не может.
Другими словами задача звучит так: у меня есть денежные купюры разного номинала, и в магазине надо купить товар без сдачи. Смогу ли я это сделать?

Comments

[haiku]

Давайте уточним тогда на всякий случай - дан именно массив или все-таки множество? Элементы могут повторяться? (Просто любопытно)

[AigizK]

Pflhaiku: Задача выглядит так: люди приходят в магазин, у каждого в кошельке есть купюры. У кого то много, у кого то мало. Есть крупные, так и мелкие купюры. Вам надо купить товар без сдачи. Надо выяснить, можете ли вы это сделать. Если да, то какие купюры использовали.

Answer 1

[Mrrl]

В вашем примере каждое из чисел, кроме 5, делится на предыдущее. Поэтому, до определённого момента - пока осталось заплатить не меньше 10 руб, и в кошельке есть купюры не меньше 10 - можно пользоваться "жадным" алгоритмом - брать самую большую купюру, которая меньше остатка стоимости товара.
Допустим, что остались только монеты по 1,2,5 руб. Если есть хотя бы одна монета 1 руб - то платить пятирублёвой монетой безопасно, даже если останется нечётная цена - то набрать её рублём и двушками удастся. Если есть две монеты по 5 руб, и осталось заплатить не меньше 10 - смело тратьте одну из них. Вторую тратить подождите, это может быть опасно.
В конце концов у вас останутся только пятачки и двушки, причём либо пятачков не более одного, либо осталось заплатить меньше десятки. Смотрите. Если надо заплатить нечётную сумму: если пятачков нет или надо заплатить 1 или 3 рубля - задача неразрешима. В противном случае тратите пятачок, остаётся чётная сумма.
Пытаетесь набрать остаток двушками. Если их хватило - вы победили. Если нет, то вам подсунули неразрешимый пример...
Если бы набор купюр и монет был из времён СССР (1,2,3,5,10,15,20,50,100,300,500,1000,2500,5000,10000), задача была бы значительно сложнее и интереснее.

UPD. Моё решение неверно. Кто найдёт контрпример?

Более правильный вариант.
- если есть хотя бы одна монета в 1 руб, то работает "жадный" алгоритм - в цикле платите самой большой купюрой, которая у вас есть и не превышает остатка суммы.
- если монеты 1 руб. нет:
- - если сумма, которую надо набрать, нечётна, а пятачка нет, вы проиграли.
- - если сумма, которую надо набрать, нечётна, и есть хотя бы один пятачок, вносим его. Переходим к следующему пункту.
- - если остаток суммы, который надо набрать, чётен - объединяем пятачки в пары (и по одному пятачку платить не будем, даже если хочется). И запускаем жадный алгоритм. Если задача разрешима, то он справится.

Comments

[AigizK]

Самый последний пункт не совсем правильный. Допустим у меня есть монеты 2,5,5,5,1000, а надо получить сумму 1007.
Ваш алгоритм: 1007-5-2*5-2=990 нет решения
Вы правильно заметили, у нас есть 2 числа нечетных. Если они отсутствуют и заданное число нечетная, то решения нет.
В противном случае жадным алгоритмом доходим до 5(если 5 вообще нет, то до конца). И дальше несколько вариантов:
1. Остаток четный, тогда 5-ки отнимаем парами. Если осталась одна 5 и есть еще единица, тогда отнимаем 5-ку и единицу, если единицы нет, то пятерку игнорируем. Продолжаем жадный алгоритм.
2. Остаток нечетный. тогда отнимаем одну 5-ку и делаем остаток четным и переходим к варианту 1

[Mrrl]

AigizK: Что-то не так. Если считать по моему алгоритму: 1007-5=1002. Следующим шагом, по жадному алгоритму, мы берём 1000. Остаётся 2, и всё решено. Брать 5*2, когда можно брать 1000, алгоритм не рекомендует. Когда мы "объединяем пятачки в пары", то они остаются в кошельке, пока до них не дойдёт очередь.

[Mrrl]

AigizK: А в вашем варианте (он практически совпадает с моим неправильным) - попробуйте рассмотреть пример 10,5,2,2,2,2, надо получить 13.

[AigizK]

Т.е. если у нас нечетное число, нам в первую очередь надо его превратить в четное. Для этого надо отнять одну 5,если нет, то единицу.Для четных применяем жадный алгоритм до 5. А дальше 5-ку вычитаем одновременно или с другой 5-ой или с единичкой, чтоб остаток всегда был четным. Если остается одна пятерка, то его пропускаем дальше продолжаем жадный алгоритм. Вроде так правильно.
Спасибо большое, спасли от ненужных транзакций при конвертации монет ))

[Mrrl]

AigizK: Не так. Если есть хотя бы одна единица, то надо вообще ни о чём не думать. Ваш вариант сломается на примере "10,5,1, надо получить 11". Он увидит нечётное число и попытается взять пятёрку, что будет ошибкой.

[AigizK]

Mrrl: Понял, спасибо

Answer 2

[Армянское Радио]

Берете программу, которая перебирает все возможные сочетания чисел из массива и считает суммы.

Способ перебора сочетаний - берете число в двоичной системе счисления, в котором цифр столько, сколько у вас элементов массива.

Пробегаете массив и цифры двоичного числа. Если в числе 1, добавляете элемент массива к сумме. Если сумма сошлась - ура, иначе продолжаете перебор.

Comments

[AigizK]

Перебор рассматриваю в последнюю очередь

[Армянское Радио]

AigizK: это вариант задачи упаковки рюкзака. Так или иначе придется перебирать. Лучшее, что можно сделать - насочинять эвристик: отсортировать массив по убыванию и пропускать варианты, когда сразу понятно, что получился перебор.

[AigizK]

дополнил условие задачи

[Армянское Радио]

Это баянище олимпиадный. Гуглить не пробовали? пост на хабре

[AigizK]

Олимпиадный вариант не подходит, там купюр не ограниченное количество. За наводку упаковки рюкзака спасибо. Один из подвидов этой задачи идентична с моей задачей

[Армянское Радио]

AigizK: Дубовый перебор хорош тем, что неограниченно разводится на параллельные процессы без пенальти по производительности.

[AigizK]

Армянское Радио: С учетом специфики задачи нашел способ обойтись без перебора. У меня есть купюра с достоинством 1, поэтому в любом случае могу разменять большую купюру на мелкие так, чтоб из большого получить несколько купюр, в сумме которые они дают мне нужное число. Так же в системе есть некий центробанк, с неограниченным количеством денег любого номинала. Из своего кошелька вычитаю как предложил Антон Федорян и допустим набралась сумма 8, нужно набрать 10,а у меня есть купюра номинала 5, я его размениваю в центробанке на мелкие купюры, с обязательным условием чтоб мог получить любым способом 2(скажем 1+1 или просто 2),центробанк мне высылает допустим монеты 2,2,1 и одну двойку я использую.

Answer 3

[Антон Федорян]

Как вариант, начинайте перебором вычитать из B числа массива, начиная с конца.
Например: B=10, А=[2,3,5,5,7]
10 - 7 = 3
Если 3 есть в А, то хорошо.
Дальше...
10 - 5 = 5...
Надеюсь понятно объяснил.

UPD: число В не должно быть больше суммы чисел в массиве.
UPD1: также нужно еще разницу чисел проверять на вхождения из массива. Сумбурно наверно описал все.

Answer 4

[Sergey Lerg]

Перебором, использовать алгоритм последовательной генерации сочетаний из массива. Вот, например, реализация infostart.ru/public/240261