logo标签列表

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

crecursioncombinationsdynamic-programming
6
我很少接触动态规划。我用它来解决DNA对齐问题、基本背包问题和简单的路径查找问题。我理解了它们的工作原理，但我还不是完全熟悉它。我有一个问题让我想起了0-1动态规划，但是由于有所不同，我不确定是否仍然可以使用这种技术，或者我必须采用递归方法。
假设我有一个项目列表，每个项目都有不同的价值、重量和成本。可能会有多个相同的项目。假设我必须选择一个组合，其中价值最高，但仍在重量和成本的限制范围内。到目前为止，我已经描述了背包问题，基本上有两个约束条件。但是这里有一个区别：所选项目的价值取决于我在组合中拥有多少个该项目。
假设每个项目都有一个与之相关的函数，告诉我一组这些项目对我的价值是多少。这是一个基本的线性函数，例如value_of_item = -3（该项数量）+50。因此，如果我在组合中有1个某个项目，则对我而言，它的价值为47。如果我有2个，则它们对我而言只有44的价值。
如果我对此使用动态规划表，那么对于每个单元格，我都必须回溯以查看该项目是否已经在当前组合中，这使得DP毫无意义。但也许有一种方法可以重新构建问题，以便我可以利用DP的优势。
希望这讲得清楚。另一种选择是生成成本和重量限制内的所有项目组合，计算每个组合的价值，选择最有价值的组合。即使对于1000个项目的列表，这也将是一个昂贵的搜索，而且我会反复计算它。我想找到一种利用DP优势的方法。
DP的本质是执行计算，然后允许快速查找未来计算的结果。这需要在表示输入条件的某些唯一数字和该条件集的计算成本之间进行映射。如果我有2个红色和3个绿色，以及4个蓝色，我可以将所有可能的组合唯一编号为：r = 红色数量，g = 绿色数量，b = 蓝色数量，id = r *（3 * 4）+ g * 4 + b。我可以使用id来查找缓存的计算结果。 - Speed8ump
1个回答
0
如果您的函数形式为：
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 < j。

反证法证明：假设存在这样一个最优解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的方法。

在此主题中的一些研究（更一般）：

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接