我可以使用动态规划来解决这个问题吗？

Question

我对动态规划的经验很少。我用它解决了一个 DNA 对齐问题、一个基本的背包问题和一个简单的寻路问题。我了解它们是如何工作的，但这并不是我感到绝对舒服的事情。

我有一个让我想起 0-1 动态规划的问题，但差异让我失望了，我不确定我是否仍然可以使用这种技术，或者我是否必须接受递归方法。

假设我有一个项目列表，每个项目都有不同的值(value)、重量和成本。每个项目可能不止一个。

假设我必须从这些元素中选择一个最有值(value)的组合，但要保持在重量和成本的限制范围内。到目前为止，我已经描述了背包问题，几乎有 2 个约束。但区别在于:

所选项目的值(value)会根据组合中的项目数量而变化。

假设每个项目都有一个与之关联的功能，它告诉我一组这些项目对我来说值多少钱。它是一个基本的线性函数，例如value_of_item = -3(该项目的数量)+ 50

因此，如果我在组合中有 1 个元素，那么它对我的值(value)是 47。如果我有 2 个，那么它们对我来说每个只值 44。

如果我为此使用动态编程表，那么对于每个单元格，我都必须回溯以查看该项目是否已经在当前组合中，从而使 DP 毫无意义。但也许有一种方法可以重新构建问题，这样我就可以利用 DP。

希望这是有道理的。

另一种方法是生成每个元素的组合，在成本和重量的限制内，计算每个组合的值(value)，选择最有值(value)的组合。即使对于包含 1000 个项目的列表，这将是一个昂贵的搜索，而且我会反复计算它。我想找到一种方法来利用 DP 的优势。

Answer 1

如果你的函数是这样的

value(x, count) = base(x) - factor(x) * count, factor(x) > 0,

然后你可以通过拆分项目将问题减少到标准背包:

x -> x_1 to x_max_count
value_new(x_i) = value(x, i)
weight(x_i) = weight(x)

现在您可以轻松验证新问题的最佳解决方案是否使用了某些项目 x_j，而不是使用每个 x_i 和 i

反证法:假设存在这样一个最优解S，它使用x_j，而不是x_i，j > i。然后有一个替代解决方案 S'，它使用 x_i 而不是 x_j。因为 j > i,

value_new(x_j) = value(x, j) 
               = base(x) - factor(x) * j 
               < base(x) - factor(x) * i
               = value(x, i)
               = value_new(x_i)

因此 S' 的值高于 S，我们得出了矛盾。

此外，我们可以允许factor(x) = 0，这对应于一个标准的背包元素。

但是如果有形式的约束

value(x, count) = base(x) + factor(x) * count

其中 factor(x) 是一个任意值，上面的解决方案不再有效，因为最后一项将是具有最大值的那个。也许对 DP 进行一些复杂的修改可能允许您使用此类约束，但我没有看到对问题本身进行任何修改以立即使用 DP。

该主题的一些研究(更一般):

• http://dept.cs.williams.edu/~heeringa/publications/knapsack.pdf
• http://clweb.csa.iisc.ernet.in/vsuresh/Kamesh-PLKP.pdf