Как узнать все числа из всех вариаций при минимальном кол-ве операций?

Question

[vitaliyVH]

У нас есть 100 известных чисел (12 56 84 15 и т.д) и есть отдельное число, к примеру 40. Нужно найти все вариации из 10 известных чисел среднее которых будет меньше отдельного числа 40

Comments

[xmoonlight]

vitaliyVH,
Ух ты! Где такие задачки задают?
Можете подсказать? (хотелось бы потренироваться немного)

[vitaliyVH]

xmoonlight, задание под один проект, требуется как это решить при минимальной затрате времени, для реализации 1-й задачи

[vitaliyVH]

xmoonlight, забыл ответить, тематика проекта, поиск неэффективностей на рынке, с попыткой извлечь из этого прибыль. Рынок игровых вещей, проект под личные нужды

[xmoonlight]

vitaliyVH, а-а, понял. Да. Вроде, все верно делаете! (у меня не было этой версии тематики :)
Удачи Вам!

[vitaliyVH]

xmoonlight, спасибо, и вам тоже успехов!

Answer 1

[xmoonlight]

Сначала нужно отсеять все варианты средних (эвристика).
Для этого нужно знать:
1. Могут ли повторяться числа
2. Что значит (система из неравенств): среднее для N чисел в отношении (больше/меньше) к заданному.

Comments

[vitaliyVH]

Благодарю за ответ

[xmoonlight]

vitaliyVH, Не за что...
(тематика проекта, если ни секрет, какая?)

Answer 2

[vaut]

Задача об упаковке рюкзака.
Среднее меньше 40 то же самое что сумма меньше 400.
Ну а дальше ничего сильно лучше перебора не существует.

Comments

[vitaliyVH]

перебор к сожалению занимает слишком много операций, разве нет альтернативного метода?

[vaut]

vitaliyVH, ключевые слова "задача об упаковке рюкзака" можете найти довольно много статей об оптимизации перебора (отбрасывании заведомо не подходящих решений).
Я немного не прав, у вас немного другая задача, но явно не менее затратная в вычислениях.
Классическая задача требует найти максимально близкое к пределу заполнение. Но так как ваша задача сводится к этой простым поиском максимума, то она не может решаться быстрее....

[vitaliyVH]

Спасибо за ответ, буду думать. Хорошего дня.

[Lynn «Кофеман»]

Не, это гораздо проще рюкзака

Сортируем числа по возрастанию и берём первые 10, потом первые 9 и 11 и т.д. пока среднее не превысит 40. Всё

[Роман]

Алексей Тен, а как же вторые 10 и т.д.? )))

[longclaps]

Алексей Тен, ваш стремительный ответ так же победителен, как начало известного доказательства Великой Теоремы Фрема: "главная идея - переносим x^n в правую часть уравнения" )

[Lynn «Кофеман»]

Роман, longclaps, ну понятно что дальше перебор, но он сто раз описан и вполне конечен. Т.е. каждая десятка это один из подходящих ответов и не нужно перебирать все(!) комбинации из 100 по 10.

[longclaps]

Алексей Тен, нет. Аккуратный анализ покажет, что овчинка выделки не стоит.

[Lynn «Кофеман»]

longclaps, ну может там такой набор чисел, что под условие подпадает всего несколько вариантов. Если распределение реально равномерное, то конечно совершенно без разницы как перебирать эти триллионы вариантов

[Ordec]

Алексей Тен, можно просто взять отсортированный массив с 0 по n<=40, и все суммы из 10 в этом массиве будут решением.

[Андрей]

Один из вариантов оптимизации, не суммировать каждый раз 10 чисел, а сумму 9 сохранять, подменяя только 1 число за раз, т.е. вычитая прежний вариант и суммируя следующий. сумма каждый раз должна быть менее 400, иначе вариант сразу не годится.