0

我想在 theta 表示法中找到以下背包自上而下方法算法的运行时间

KNAPSACK-TOP-DOWN(T, U )
     if U < 0 then return −∞
     else if T = ∅ or U = 0 then return 0
     else
         Let t = v, w be the last entry in T
         m1 ← KNAPSACK-TOP-DOWN(T − {t}, U )
         m2 ← v + KNAPSACK-TOP-DOWN(T − {t}, U − w)
         return max{m1 , m2 }

我相信这个问题的上限是 O(2^n)。如何找到渐近紧界？

4

1 回答 1

4

您的伪代码代表了背包问题的幼稚解决方案。看到它的结构很像天真的斐波那契实现，即O(2^n). 事实上，背包的幼稚实现是指数级的。请记住，有一个无界背包问题可以通过O(uT)动态规划来解决。

至于为什么这个实现是指数级的，首先，请记住，递归调用的数量会随着增加T而增加。U然后注意算法的每次迭代都会递归调用 KNAPSACK-TOP-DOWN 两次，在最坏的情况下会调用 KNAPSACK-TOP-DOWN 两次，依此类推。

                              (T, U)                                        1
                            /        \
                           /          \
                          /            \
                         /              \
                        /                \
              (T-{t},U)                    (T-{t},U-w)                      2
            /           \                /             \
           /             \              /               \
(T-{t}-{t'},U) (T-{t}-{t'},U-w)  (T-{t}-{t'},U-w) (T-{t}-{t'},U-w-w')       4
                                                                            8
                                                                            16
                                                                            ...

如您所见，递归调用的数量根据背包的物品数量和容量呈指数增长。另请注意T，在最坏的情况下，将引入一个全新的“级别”，其中的新元素的计算量是前一个级别的两倍……当然，这只有在背包中有足够的容量时才会发生，所以 T 和 U 都会影响计算的数量。看看上面的树，很明显，幼稚的实现确实是O(2^n).

But if you look attentively at the "stacktrace" you will notice that (T-{t}-{t'},U-w) (and consequently, all of its subproblems) is being called twice. This is where Dynamic Programming kicks in. We can store the computed results in some kind of data structure and further look them up so that the same subproblems don't need to be computed twice. When using this approach things drastically speed up and the whole problem can be computed in time proportional to the capacity of the knapsack * the amount of items to be considered, or, in theta notation, O(uT)

本文提供了 naive 和O(uT)版本的 C 实现。如果您的问题与家庭作业有关，您应该明确地查看它。最后，搜索“背包问题”会教你很多关于 NP-complete、NP-Hard、伪多项式时间等的知识。

于 2013-09-29T05:43:01.300 回答