当$ v_i= i $时，kackasack问题是np - 硬吗？

Question

背包问题是NP - 硬，可以制定为： $$ \ begin {aligh}＆\ text {maximize} \ sum_ {i= 1} ^ n v_i x_i，\ tag {p1} \\＆ \ text {that} \ sum_ {i= 1} ^ n w_i x_i \ leq w，\\＆\ text {and} x_i \ in \ {0,1 \}。\结束{aligh} $$

如果 $ v_i= i $ ？它仍然是np-hard吗？

$$ \ begin {align}＆\ text {maximize} \ sum_ {i= 1} ^ n ix_i，\标记{p2} \\＆ \ text {that} \ sum_ {i= 1} ^ n w_i x_i \ leq w，\\＆\ text {and} x_i \ in \ {0,1 \}。\结束{aligh} $$

我试图减少（p1）到（p2）。给定（p1）的实例，我创建相同数量的项目，同一权重。现在，我必须将解决方案与（P1）和（P2）联系起来。

Answer 1

否，此问题在 $ \ mathbf {p} $ 中。主要点是所有值的总和是 $ 1 + 2 \ ldots + n=frac {n（n + 1）} {2}=mathcal {o}（ n ^ 2）$ ，它是输入大小的多项式。如果没有额外限制 $ v_i= i $ ，则所有值的总和都可以在输入大小中指数，因为该值在输入中以二进制表示。

所以我们可以定义 $ dp [i] [v] $ ，其中 $ 1 \ leq i \ leq n $ 和 $ 0 \ leq v \ leq \ frac {n（n + 1）} {2} $ ，为获得值所需的最小权重至少 $ v $ ，仅使用第一个 $ i $ 项目。如果无法实现，我们将设置 $ dp [i] [v]= Inf $ 。最终答案是最大 $ v $ ，使得 $ dp [n] [v] \ Leq W $ 。

可以按如下方式计算DP值：

$ dp [i] [v]= min（dp [i-1] [v]，w_i + dp [i-1] [v - v_i]）$ 。

第一个术语考虑 $ i ^ {th} $ 项目未被选中，第二个术语是它被选中的可能性。< / p> 所以整个问题可以在 $ \ mathcal {o}（n ^ 3）$ 时间和 $中\ mathcal {o}（n ^ 3）$ 空格，可以减少到 $ \ mathcal {o}（n ^ 2）$ 空间只是重用两个大小阵列 $ \ frac {n（n + 1）} {2} + 1 $ 。