Вариация задачи о сдаче
От: Sinclair Россия https://github.com/evilguest/
Дата: 17.01.23 13:56
Оценка:
Внезапно возникла такая задача:
1. Есть некоторое множество попарно различных целых чисел. Например, 2, 5, 10, 11, 13, 14, 17
2. Нужно выбросить из неё те числа, которые представимы в виде линейной комбинации (с целыми коэффициентами) других чисел. В нашем примере остаются 2 и 5.

Эта задача похожа на задачу о сдаче
Автор: мыщъх
Дата: 22.07.10
: если отсортировать исходную последовательность во возрастанию, то она сводится к вопросу "можно ли разменять число набором монет с номиналами, представленными левее в списке"? То есть нас не интересует ни само количество вариантов, ни поиск варианта с минимальным количеством монеток.
Просто нужно знать — есть ли такой вариант или нет.

Есть идеи, куда копать?
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.