0/1背包与非理性的权重 [英] 0/1 Knapsack with irrational weights

问题描述

考虑 0/1背包问题。 标准的动态规划算法仅适用于当容量以及权重来填充与背包是整数/有理数。你会怎么做时，容量/重量是不合理的？

Consider the 0/1 knapsack problem. The standard Dynamic Programming algorithm applies only when the capacity as well as the weights to fill the knapsack with are integers/ rational numbers. What do you do when the capacity/weights are irrational?

问题是，我们不能memoize的像我们这样的整数权重，因为我们可能需要潜在的无限小数非理性的权重 - 导致一个无限大的列数的动态规划表。

The issue is that we can't memoize like we do for integer weights because we may need potentially infinite decimal places for irrational weights - leading to an infinitely large number of columns for the Dynamic Programming Table .

有没有解决这个任何标准的方法？对这个问题的复杂性，任何意见？任何启发？

Is there any standard method for solving this? Any comments on the complexity of this problem? Any heuristics?

什么样（例如）相关的复发：
函数f（x）= 1，对于x＆所述;的sqrt（2）

函数f（x）= F（X-的sqrt（2））+ SQRT（3），否则 ？

What about associated recurrences like (for example):
f(x)=1, for x< sqrt(2)

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

或者这里Pibonacci号问题： http://www.spoj.pl/problems/PIB/ 的？

Or the Pibonacci number problem here: http://www.spoj.pl/problems/PIB/ ?

推荐答案

我不知道这将解决你所说的那种问题的任何一般方法。也许在Pibonacci使用的记忆化技术（见下面第二部分）可以被使用。

I don't know of any general method which will solve problems of the kind you stated. Perhaps the memoization technique used in Pibonacci (see second section below) can be used.

在任何情况下，有时，我们可以利用这个问题（见的sqrt（2）及开方（3））得到真正快速的算法。下面的解决方案

In any case, sometimes, we can give really fast algorithms by exploiting the problem (see the sqrt(2) & sqrt(3)) solution below.

减少这种问题，背包可能不是一个好主意，因为我预计将有哪些会快很多其他的方式。

Reducing such problems to knapsack might not be such a good idea as I expect there will be other ways which will be much faster.

因此​​，要回答你的问题：

So to answer your questions:

问题涉及的sqrt（2）和SQRT（3）

我先回答你的第二个问题。

I will answer your second question first.

f(x) = 1 for x < sqrt(2). (x >= 0 also, I presume)
f(x) = f(x-sqrt(2)) + sqrt(3)

这是可以解决的非常快（在O（登录LOGN）的时间！），只使用整数运算（假设O（1）），期待它需要通过开方乘最后一个步骤（3），并加入1

This can be solved very fast (in O(log logn) time!), using only integer arithmetic (which is assumed O(1)), expect for one last step which requires multiplying by sqrt(3) and adding 1.

由于我们需要找到最小米的N使得

Given an n we need to find the smallest m such that

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 *开方的整数部分（2）

和我们有F（N）=（M-1）* SQRT（3）+ 1

and we have that f(n) = (m-1)*sqrt(3) + 1.

因此​​，我们只需要计算 [N *开方（2）] 的 N *开方的整数部分（2）。

Thus we only need to calculate [n *sqrt(2)] the integer part of n*sqrt(2).

这可以通过使用连分数的sqrt（2），这是合理的近似​​SQRT（2），他们是在某种意义上与给定的分母尺寸最好的近似。

This can be quickly calculated by using the Continued Fractions of sqrt(2) which are rational approximations to sqrt(2) and they are in some sense the 'best' approximations with given denominator sizes.

连分数开方的（ⅰ）/ B（1）（2）可以使用复发来形成：

The continued fraction a(i)/b(i) of sqrt(2) can be formed using the recurrence:

a0 = 1
b0 = 1
a(i+1) = a(i) +2*b(i)
b(i+1) = a(i) + b(i)

可以看出，在以近似[N * SQRT（2）]就足够了考虑一些奇的量B（1）> 10 * N ^ 2（使用的刘维逼近定理和连分数定理），而 [N *开方（2）] = [N * A（I）/ B（1）] 为我。

It can be shown that in order to approximate [n*sqrt(2)] it is enough to consider some odd i for which b(i) > 10*n^2 (using Liouville's approximation Theorem and theorems on continued fractions) and that [n*sqrt(2)] = [n*a(i)/b(i)] for that i.

现在一个（i）中，B（1）满足矩阵方程

Now a(i), b(i) satisfies the matrix equation

[1 2] [a(i)]    [a(i+1)]
[1 1] [b(i)]  = [b(i+1)]

因此​​，我们需要计算矩阵幂

Thus we need to compute powers of the matrix

[1 2]
[1 1]

因此​​，该项目获得大于10 * N ^ 2。

So that the entries get bigger than 10*n^2.

可以示出，该基体的所需要的功率为O（logn）时间，因此可以在O计算值（日志log n）的使用仅整数算术时间（假设是O（1））。

It can be shown that the required power of the matrix is O(logn) and thus can be calculated in O(log log n) time using only integer arithmetic (assuming that is O(1)).

因此​​，在n您的函数f值可以在O计算仅使用整数运算（除了最后一步，在这里你需要通过开方乘整数（3））（日志LOGN）的时间。

So the value of your function f at n can be calculated in O(log logn) time using only integer arithmetic (except for the last step, where you need to multiply an integer by sqrt(3)).

Pibonacci号

从您的意见，这就是问题所在。

From your comment, this is the problem

g(x) = 1 if 0 <= x < 4
g(x) = g(x-1) + g(x-pi) x >= 4

这使用记忆化可以解决的：

This can be solved using memoization:

让 H（M，N）= G（M - N * PI）

然后，我们有

h(m,n) = h(m-1, n) + h(m, n+1)

因此​​，我们有

And so we have that

g(m) = g(m-1) + h(m, 1)

您现在可以通过维护两个表，一个是G（M）等为H（M，N）使用记忆化。请注意，即使你需要计算 H（M，N + 1），提高氮肥不仅降低米-n * pi和一个合理的时间内从0到4将成为（O（M）我想），这样你就不会永远保持回事。

You can now use memoization by maintaining two tables, one for g(m) and other for h(m,n). Note that even though you need to calculate h(m,n+1), increasing n only reduces m -n*pi and will become between 0 and 4 within a reasonable time (O(m) I suppose), thus you won't keep going on forever.

这是不是漂亮（或快速）的平方根（2）和SQRT（3）解决方案，但我相信它确实给一个方式做了计算。

This is not as nice (or fast) as the sqrt(2) and sqrt(3) solution, but I believe it does give a way to do the calculation.

0-1背包与无理系数

也许考虑好合理的近似无理，然后求解近似0-1背包问题最终会收敛到正确的解决方案。

Perhaps taking better and better rational approximations to the irrationals and then solving the 0-1 knapsack problem for approximation will ultimately converge to the right solution.

我的猜测是，在本次迭代的定点会给你的解决方案。

My guess is, the fixed point in this iteration will give you the solution.

当然，作为近似得到更好，他们的O（NW）在W动态规划算法有可能成为指数很快，你可能会更好只考虑所有的可能性。

Of course, as the approximations get better the W in O(nW) of they dynamic programming algorithm might become exponential soon and you might be better off just consider all possibilities.

这篇关于0/1背包与非理性的权重的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！