algorithm - 0/1 重量不合理的背包

Question

考虑 0/1 knapsack problem .标准动态规划算法仅适用于背包的容量和重量为整数/有理数的情况。当容量/重量不合理时你会怎么做？

问题是我们不能像对整数权重那样进行内存，因为我们可能需要无限的小数位来表示无理权重 - 导致动态规划表的列数无限大。

有解决这个问题的标准方法吗？对这个问题的复杂性有何评论？有启发式吗？

关联的重复情况如何(例如):

f(x)=1, for x< sqrt(2)


f(x)=f(x-sqrt(2))+sqrt(3),otherwise
？

或此处的 Pibonacci 数问题:http://www.spoj.pl/problems/PIB/ ？

Answer 1

我不知道有什么通用方法可以解决您所说的问题。也许可以使用 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)的整数部分即可。

这可以通过使用 Continued Fractions 来快速计算。 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)]，考虑一些 b(i) > 10*n^2 的奇数 i 就足够了(使用 Liouville's approximation Theorem 和连分数定理) 和那个 [n*sqrt(2)] = [n*a(i)/b(i)] 对于那个 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) I假设)，因此你不会永远继续下去。

这不如 sqrt(2) 和 sqrt(3) 解决方案好(或快)，但我相信它确实提供了一种进行计算的方法。

---

0-1 带无理系数的背包

也许对无理数采取越来越好的有理逼近，然后解决 0-1 背包问题进行逼近，最终会收敛到正确的解决方案。

我的猜测是，此迭代中的不动点将为您提供解决方案。

当然，随着近似值越来越好，O(nW) 中的 W 动态规划算法可能很快就会呈指数增长，考虑所有可能性可能会更好。