Внезапно возникла такая задача:
1. Есть некоторое множество попарно различных целых чисел. Например, 2, 5, 10, 11, 13, 14, 17
2. Нужно выбросить из неё те числа, которые представимы в виде линейной комбинации (с целыми коэффициентами) других чисел. В нашем примере остаются 2 и 5.
Эта задача похожа на
задачу о сдачеАвтор: мыщъх
Дата: 22.07.10
: если отсортировать исходную последовательность во возрастанию, то она сводится к вопросу "можно ли разменять число набором монет с номиналами, представленными левее в списке"? То есть нас не интересует ни само количество вариантов, ни
поиск варианта с минимальным количеством монеток.
Просто нужно знать — есть ли такой вариант или нет.
Есть идеи, куда копать?