Здравствуйте, xma, Вы писали:

xma>натуральных или неотрицательных целых ?
неотрицательных.


xma>a*2 = 3, (для проверки числа 3)
Для пары чисел это сводится просто к кратности
xma>a*2 + b*3 = 5, (для проверки числа 5)
Ага.
xma>a*2 + b*3 + c*5 = 10, (для проверки числа 10)
Ага.

xma>ну и числа которые являются линейной комбинацией других — можно наверное сразу удалять и не добавлять в новое уравнение (для последующих чисел)
Да, конечно.

S>>Натуральные.
xma>а сами числа (не коэффициенты) — натуральные и большие единицы, я так понимаю ?
Да, если минимальный равен единице то решение тривиально.

Здравствуйте, gandjustas, Вы писали:

G>a=0, b=1, c=3, d=0
G>Несложно перебирается даже в уме. Почему компьютеру не доверить эту задачу?

можно конечно доверить, если скорость неважна — но твоё решение почти на два (а то и почти три) порядка медленнее чем требуется автору .. (подробнее, тут

Автор: xma
Дата: 17.01.23

)

Здравствуйте, Sinclair, Вы писали:

S>Ага.

ну т.е. я так понял что затруднений с решением линейных диофантовых уравнений с произвольным числом неизвестных — теперь у тебя нету (в целых числах), но ты пока ищешь подход к решению их в неотрицательных целых ? (для коэффициентов)

Здравствуйте, xma, Вы писали:

xma>Здравствуйте, Sinclair, Вы писали:

S>>Ага.

xma>ну т.е. я так понял что затруднений с решением линейных диофантовых уравнений с произвольным числом неизвестных — теперь у тебя нету (в целых числах), но ты пока ищешь подход к решению их в неотрицательных целых ? (для коэффициентов)

xma>
Ага. Впрочем, есть подозрение, что это лютый оверкилл, т.к. перебор вполне себе работает даже и без мемоизации.

Здравствуйте, xma, Вы писали:

xma>Здравствуйте, gandjustas, Вы писали:

G>>Вот накидал перебором для 50 до 1000 чисел https://dotnetfiddle.net/q51ICI
G>>С 50 числами до 1000 работает за 0.1, с числами до 1М за 0.14
xma>батенька, у тебя код выполняется — сотни миллисекунд а надо в пределах одной миллисекунды (пруф

Автор: Sinclair
Дата: 17.01.23

)
Нет там никаких сотен. https://dotnetfiddle.net/EJ8xem
Чтобы добраться до 1мс, пришлось увеличить и максимум и количество чисел в 10 раз. И это — без мемоизации.

xma>до миллисекунды вряд ли "тупым перебором" можно до оптимизировать

уже

Здравствуйте, Sinclair, Вы писали:

S>Здравствуйте, xma, Вы писали:

xma>>Здравствуйте, gandjustas, Вы писали:

G>>>Вот накидал перебором для 50 до 1000 чисел https://dotnetfiddle.net/q51ICI
G>>>С 50 числами до 1000 работает за 0.1, с числами до 1М за 0.14
xma>>батенька, у тебя код выполняется — сотни миллисекунд а надо в пределах одной миллисекунды (пруф

Автор: Sinclair
Дата: 17.01.23

)
S>Нет там никаких сотен. https://dotnetfiddle.net/EJ8xem
S>Чтобы добраться до 1мс, пришлось увеличить и максимум и количество чисел в 10 раз. И это — без мемоизации.
Не то измерено, filtered лениво вычисляется

xma>>до миллисекунды вряд ли "тупым перебором" можно до оптимизировать
S>уже
Я пооптимизировал децл, 20 мс получилось https://dotnetfiddle.net/q51ICI
Мемоизация не особо помогла.

Здравствуйте, gandjustas, Вы писали:

G>Я пооптимизировал децл, 20 мс получилось https://dotnetfiddle.net/q51ICI

я тоже "по оптимизировал" — и поставил 50 чисел рандомом от 2 до 100 млн (каждое число),

итого, сотни миллисекунд — и ладно бы сотни, результат гуляет (числа то рандомные) и порой до 2х секунд доходит
https://dotnetfiddle.net/1sAGAD

P.S.:

если чисел 500 (от 2 до 100 млн каждое), то результата не дождался

если чисел 50 (от 2 до 1 млн каждое), то результата за несколько десятков ms

P.S.2:

но вообще да, если 50 чисел (от 2 до 10 тыс каждое), то 2-3 ms выполняется код
https://dotnetfiddle.net/CV6BK6

Здравствуйте, Sinclair, Вы писали:

S>Внезапно возникла такая задача:
S>1. Есть некоторое множество попарно различных целых чисел. Например, 2, 5, 10, 11, 13, 14, 17
S>2. Нужно выбросить из неё те числа, которые представимы в виде линейной комбинации (с целыми коэффициентами) других чисел. В нашем примере остаются 2 и 5.

S>Эта задача похожа на задачу о сдаче

Автор: мыщъх
Дата: 22.07.10

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

S>Есть идеи, куда копать?


Похоже на основную задачу линейного программирования, но не она.
Поэтому следующая идея, может пригодится. Предупреждаю, что не проверял, "as is", no warranty.

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

Обозначим исходное множество, сразу будем считать его упорядоченным по возрастанию, как М.
Обозначим результирующее мн-во как B (база).
Если для числа x выполняется пункт 2. относительно B, то будем говорить что x представимо (с натуральными весами) в B.


Алгоритм: вначале B пустое. Множество М содержит m элементов.
* Берем первый (наименьший) эл-т e0 из M и переносим его в B.
* Теперь перетащим из M в B все минимальные элементы x с различными значениями (x mod e0). Для этого проходим по M и
если для элемента i выполнено (i mod e0)=0 или (i mod e0)=(b mod e0) для некоторого эл-та b из B, то просто выбрасываем i из M,
иначе переносим i в B.
Очевидно, что по дороге если мы накопили e0 элементов в B, то дальше можно просто занулить M, т.к. все остальное не добавит
ничего в B.
* По окончании предыдущего шага М пустое и B является базой для исходного полного M, при этом любой элемент из M представим
максимум двумя элементами (с натуральными весами) из B.

Сложность по времени O(m). Чем ближе e0 к 1, тем лучше.