对确切所需项目编号约束的背包问题

Question

如果我们现在必须通过常量 $ l $ ？这是相同的问题（ $ w $ ，每个项目都有一个值 $ v $ 权重 $ w $ ），但必须添加完全 $ l $ 项目（s）背包（显然需要优化背包的总价值）。

我所考虑实施这一点（动态编程，蛮力）导致失败，或宇宙寿命的级别计算时间。任何帮助或想法都受到赞赏。

编辑：我正在寻找伪多项式时间解决方案

Answer 1

您可以将此问题转换为背包的实例。让 $ n $ 是项目数， $ v $ 是项目的最大值和假设每个项目的重量为大多数 $ w $ （否则它可以被丢弃）。

要确保至少选择 $ l $ 项目：

• add $ n（v + 1）$ 到每个项目的值。
现在，问题相当于最大化所选项目的数量，断开具有最大原始总值的一组项目的关系，而受重量约束。有一个解决方案至少选择 $ l $ 项目iff最佳解决方案至少具有 $ n（v +1）l $ 。

以确保您选择最多 $ l $ 项目：

• add $（w + 1）$ 到每个项目的权重。
• add $ l（w + 1）$ 到 $ w $ 。
现在，超过 $ l $ 项目的每个子集至少重 $（l + 1）（w + 1 ）= L（w + 1）+（w + 1）> l（w + 1）+ w $ ，因此不可行。 $ l $ 具有 $ w $ 的总重量的项目，现在称为 $ l（w + 1）+ w $ ，因此是可行的iff $ w \ le w $ 。 即使其总重量超过 $ w $ $ n（v + 1）l $ 。