考虑0/1背包问题.标准动态编程算法仅适用于填充背包的容量和权重是整数/有理数.当容量/重量不合理时你会怎么做？
问题在于我们不能像对整数权重一样进行memoize,因为我们可能需要无限权重的无限小数位 - 导致动态编程表的列数无限大.
有没有解决这个问题的标准方法？对此问题的复杂性有何评论？任何启发式？
那些相关的重现如(例如):
f(x)=f(x-sqrt(2))+sqrt(3),otherwise
f(x)=1, for x< sqrt(2)
f(x)=f(x-sqrt(2))+sqrt(3),otherwise
f(x)=1, for x< sqrt(2)
？
或者这里的Pibonacci数问题:http://www.spoj.pl/problems/PIB/？
小智 5
我不知道任何一般方法可以解决你说的那种问题.也许可以使用Pibonacci中使用的记忆技术(参见下面的第二部分).
在任何情况下,有时候,我们可以通过利用下面的问题(参见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).
这可以通过使用sqrt(2)的连续分数来快速计算,它是sqrt(2)的有理逼近,并且它们在某种意义上是给定分母大小的"最佳"近似值.
使用递归可以形成sqrt(2)的连续分数a(i)/ b(i):
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(使用Liouville的近似定理和连续分数的定理)和[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(1))在O(log log n)时间内计算.
因此,函数f在n处的值可以使用整数运算在O(log logn)时间内计算(除了最后一步,您需要将整数乘以sqrt(3)).
Pibonacci数
从您的评论中,这是问题所在
g(x) = 1 if 0 <= x < 4
g(x) = g(x-1) + g(x-pi) x >= 4
这可以使用memoization来解决:
让 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)
您现在可以通过维护两个表来使用memoization,一个用于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 in O(nW)很快就会变成指数,你可能会考虑所有可能性.