Я не знаю ни одного общего метода, который бы решал проблемы, о которых вы говорили. Возможно, будет использована техника запоминания, используемая в Пибоначчи (см. Второй раздел ниже).
В любом случае, иногда мы можем дать действительно быстрые алгоритмы, используя проблему (см. Решение sqrt (2) и sqrt (3) ниже.
Сокращение таких проблем до ранца может быть не очень хорошей идеей, так как я ожидаю, что будут другие способы, которые будут намного быстрее.
Итак, чтобы ответить на ваши вопросы:
Проблема, связанная с sqrt (2) и sqrt (3)
Сначала я отвечу на ваш второй вопрос.
f(x) = 1 for x < sqrt(2). (x >= 0 also, I presume)
f(x) = f(x-sqrt(2)) + sqrt(3)
Это может быть решено очень быстро (за O (log logn)!), Используя только целочисленную арифметику (которая предполагается O (1)), ожидайте один последний шаг, который требует умножения на sqrt (3) и добавления 1 .
Учитывая n, нам нужно найти наименьшее m такое, что
n - m sqrt(2) < sqrt(2)
* * Тысяча двадцать-одиной т.е.
n - m sqrt(2) < sqrt(2) => n < (m+1)*sqrt(2) => n * sqrt(2) < m+1
и
n - (m-1)sqrt(2) > sqrt(2) => n > m sqrt(2) => n*sqrt(2) > m.
Таким образом, m является целой частью n*sqrt(2)
и имеем f (n) = (m-1) * sqrt (3) + 1.
Таким образом, нам нужно только вычислить [n *sqrt(2)] целую часть n*sqrt(2).
Это можно быстро рассчитать, используя Continued Fractions из sqrt (2), которые являются рациональными приближениями к sqrt (2) и в некотором смысле являются «наилучшими» приближениями с заданными размерами знаменателя.
Непрерывная дробь a (i) / b (i) sqrt (2) может быть сформирована с использованием повторения:
a0 = 1
b0 = 1
a(i+1) = a(i) +2*b(i)
b(i+1) = a(i) + b(i)
Можно показать, что для аппроксимации [n * sqrt (2)] достаточно рассмотреть нечетное i, для которого b (i)> 10 * n ^ 2 (используя Теорема приближения Лиувилля * 1045) * и теоремы о продолженных дробях) и что [n*sqrt(2)] = [n*a(i)/b(i)] для этого я.
Теперь a (i), b (i) удовлетворяют матричному уравнению
[1 2] [a(i)] [a(i+1)]
[1 1] [b(i)] = [b(i+1)]
Таким образом, нам нужно вычислить степени матрицы
[1 2]
[1 1]
Чтобы записи были больше 10 * n ^ 2.
Можно показать, что требуемая мощность матрицы составляет O (logn) и, таким образом, ее можно рассчитать за время O (log log n), используя только целочисленную арифметику (при условии, что это O (1)).
Таким образом, значение вашей функции f при n можно вычислить за время O (log logn), используя только целочисленную арифметику (за исключением последнего шага, где вам нужно умножить целое число на sqrt (3)).
Число Пибоначчи
Из вашего комментария это проблема
g(x) = 1 if 0 <= x < 4
g(x) = g(x-1) + g(x-pi) x >= 4
Это можно решить, используя памятку:
Пусть h(m,n) = g(m - n*pi)
Тогда у нас есть это
h(m,n) = h(m-1, n) + h(m, n+1)
Итак, у нас есть это
g(m) = g(m-1) + h(m, 1)
Теперь вы можете использовать памятку, сохраняя две таблицы, одну для g (m) и другую для h (m, n). Обратите внимание, что даже если вам нужно вычислить h(m,n+1), увеличение n только уменьшает m -n * pi и станет между 0 и 4 в течение разумного времени (я полагаю, O (m)), таким образом, вы не будете продолжать вечно .
Это не так хорошо (или быстро), как решения sqrt (2) и sqrt (3), но я полагаю, что оно дает способ сделать расчет.
0-1 Рюкзак с иррациональными коэффициентами
Возможно, принятие все более рациональных и рациональных приближений к иррациональным числам, а затем решение задачи о ранце 0-1 для приближений в конечном итоге приведет к правильному решению.
Я предполагаю, что фиксированная точка в этой итерации даст вам решение.
Конечно, по мере приближения аппроксимации W в O (nW) их алгоритма динамического программирования может скоро стать экспоненциальным, и вам может быть лучше, просто рассмотрите все возможности.