Kor*_*era 6 c recursion combinations dynamic-programming
我对动态编程的经验很少.我用它来解决DNA对齐问题,基本背包问题和简单的寻路问题.我明白他们是如何工作的,但这并不是我觉得非常舒服的东西.
我有一个问题,让我想起0-1动态编程,但差异让我失望,我不确定我是否仍然可以使用这种技术,或者我是否必须采取递归方法.
假设我有一个项目列表,每个项目都有不同的值,权重和成本.每个项目可能不止一个.
假设我必须选择最有价值的那些项目的组合,但仍然在重量和成本的限制范围内.到目前为止,我已经用2个约束描述了背包问题.但这就是区别:
所选项目的值会根据我在组合中的数量而变化.
假设每个项目都有一个与之相关的功能,它告诉我这些项目的组合对我来说是多么值得.它是一个基本的线性函数,例如value_of_item = -3(该项的数量)+50
所以,如果我在一个组合中有一个项目,那么它对我的价值是47.如果我有两个,那么他们每个人的价值仅为44.
如果我为此使用动态编程表,那么对于每个单元格,我必须回溯以查看该项目是否已经在当前组合中,使得DP无意义.但也许有一种方法可以重新构建问题所以我可以利用DP.
希望这是有道理的.
另一种方法是生成每个项目组合,在成本和重量的限制内,计算每个组合的价值,选择最有价值的组合.对于1000个项目的列表,这将是一个昂贵的搜索,这是我将反复计算的东西.我想找到一种方法来利用DP的优势.
如果你的函数的形式是
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)
现在，您可以轻松验证新问题的最佳解决方案是否使用某些 item x_j，而无需使用x_ii < j 的 every 。
反证法：假设存在这样一个最优解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。
该主题的一些研究（更一般）：