Нашел на одном сайте вот такую задачку: Есть дротики в количестве m штук, есть доска, разделенная на n секторов. Есть числа A1,A2,A3...An, написанные на секторах. Требуется найти эти числа A1,A2,...An, которые нужно написать на доске, чтобы броском n дротиков (или меньшего чем n числа - ведь дротиком можно и промахнуться) теоретически можно было выбить любое число от 1 до Z. Чем больше Z - тем решение лучше. Если возможно - найти максимальное число Z. Задача по английски называется Postage Stamp Problem и является NP-полной (правда там идет речь о нахождении номиналов марок, которые надо наклеить на конверты, чтобы получилось письмо с любой стоимостью от 1 до ...) Что я уже придумал: - Случайный перебор (кстати вопреки ожиданиям - иногда именно он оказался наилучшим вариантом) - Последовательный перебор (хорош, но быстро упирается в "разумное" время перебора) - Выбор варианта наугад и улучшение одного числа, потом второго, потом третьего итд. Или сразу двух чисел - но это уже медленно - Берем вариант для n-1 секторов и ищем последний сектор для достижения наилучшего результата. Не оптимальный способ - но зато гарантированно улучшает. Данные для задачи а) 3 дротика, от 1 до 40 областей б) 4 дротика, от 1 до 30 областей в) 5 дротиков, от 1 до 20 областей г) 6 дротиков, от 1 до 10 областей Естественно, для 1 области наилучшее решение 1, так как иначе 1 будет вообще не выбить. Для двух областей лучшие решения: 1,3 (для 3 и 4 дротиков) и 1,4 (для 5 и 6 дротиков). Пока я знаю лучшие решения для 3 дротиков - до 17 областей 4 дротиков - до 10 областей 5 дротиков - до 9 областей 6 дротиков - до 8 областей Дальше никак . Или сильно медленно, или не улучшается
Я понимаю, что если задача NP-трудная, то ее можно решить только перебором. Но ее можно решить "тупым" перебором, а можно перебором с некоторыми отсечениями. Например: мы нашли решение для Z=800, следовательно, самое большое число в наборе чисел на доске должно быть > 200 (для 4 дротиков), иначе 800 не выбить при всем желании. Следовательно, если мы видим решение, где самое большое число, скажем, 180 - его можно не проверять. Когда мы улучшим решение скажем до Z=1000, можно не проверять решения с числами <250. И так далее. Других улучшений пока не придумал
Скорей всего эта задачка как-то связана с простыми числами. Например если взять 10 первых простых чисел 1, 2, 3, 5, 7, 11, 13, 17, 19, 23 То Z будет равно 210.
Z физически не может быть 210 - даже при 6 дротиках максимальное число 23*6 --> 132. Возможно при бесконечном числе дротиков это и так (не проверял), но у нас их конечное число - 3,4,5 или 6
Рассмотрим случай когда дротиков (n) меньше равно чем областей (m). В этом случае решение тривиально: A1= 2^0 A2= 2^1 A3= 2^2 A4= 2^3 ... Если дротиков больше, то нужно смотреть какие области мы можем заменить суммой нескольких попаданий на меньшие значения. Например, для n=5 m=4 имеем начальное решение: A1= 2^0 A2= 2^1 A3= 2^2 A4= 2^3 Смотрим как использовать еще один дротик, заменяем A2 комбинацией A1+A1, добавляем A5=2^4. Случай когда n=3, m=2: A1= 2^0 A2= 2^1 Убираем A2 комбинацией A1+A1, добавляем A3= 2^2. Тоесть 1 и 4, не совпадает с вашим решением. Уточните условие задачи.
Postage stamps problem (которая NP-полная) формулируется так (в терминах blueboar): даны количество секторов, количество дротиков и числа, написанные на секторах; нужно найти максимальное Z. В топике задача совсем другая: дано количество секторов, дано количество дротиков; нужно найти максимальное теоретически возможное Z и набор чисел. Подозреваю, что эта задача все-таки из класса P. Во всяком случае, для 2 секторов и любого заданного количества дротиков наилучшее решение находится за O(1) (проверено).
Составил функцию для аппроксимации на три дротика. Вот что получилось: 17 позиций: Z=284 A = 133 122 112 102 92 83 73 64 55 46 38 29 20 13 6 4 1 40 позиций: Z=898 A = 369 358 346 335 323 312 300 289 278 267 256 245 234 223 212 202 191 181 171 160 150 140 131 121 111 102 93 84 75 66 58 50 42 35 27 20 12 7 3 1 Функция имеет вид: double predict(int i) { return x*(m-i)*log(m-i)+1; } где m - количество секторов, i-индекс массива, x - подстроечный коефициент.
