我很少接触动态规划。我用它来解决DNA对齐问题、基本背包问题和简单的路径查找问题。我理解了它们的工作原理,但我还不是完全熟悉它。我有一个问题让我想起了0-1动态规划,但是由于有所不同,我不确定是否仍然可以使用这种技术,或者我必须采用递归方法。
假设我有一个项目列表,每个项目都有不同的价值、重量和成本。可能会有多个相同的项目。假设我必须选择一个组合,其中价值最高,但仍在重量和成本的限制范围内。到目前为止,我已经描述了背包问题,基本上有两个约束条件。但是这里有一个区别:所选项目的价值取决于我在组合中拥有多少个该项目。
假设每个项目都有一个与之相关的函数,告诉我一组这些项目对我的价值是多少。这是一个基本的线性函数,例如value_of_item = -3(该项数量)+50。因此,如果我在组合中有1个某个项目,则对我而言,它的价值为47。如果我有2个,则它们对我而言只有44的价值。
如果我对此使用动态规划表,那么对于每个单元格,我都必须回溯以查看该项目是否已经在当前组合中,这使得DP毫无意义。但也许有一种方法可以重新构建问题,以便我可以利用DP的优势。
希望这讲得清楚。另一种选择是生成成本和重量限制内的所有项目组合,计算每个组合的价值,选择最有价值的组合。即使对于1000个项目的列表,这也将是一个昂贵的搜索,而且我会反复计算它。我想找到一种利用DP优势的方法。
假设我有一个项目列表,每个项目都有不同的价值、重量和成本。可能会有多个相同的项目。假设我必须选择一个组合,其中价值最高,但仍在重量和成本的限制范围内。到目前为止,我已经描述了背包问题,基本上有两个约束条件。但是这里有一个区别:所选项目的价值取决于我在组合中拥有多少个该项目。
假设每个项目都有一个与之相关的函数,告诉我一组这些项目对我的价值是多少。这是一个基本的线性函数,例如value_of_item = -3(该项数量)+50。因此,如果我在组合中有1个某个项目,则对我而言,它的价值为47。如果我有2个,则它们对我而言只有44的价值。
如果我对此使用动态规划表,那么对于每个单元格,我都必须回溯以查看该项目是否已经在当前组合中,这使得DP毫无意义。但也许有一种方法可以重新构建问题,以便我可以利用DP的优势。
希望这讲得清楚。另一种选择是生成成本和重量限制内的所有项目组合,计算每个组合的价值,选择最有价值的组合。即使对于1000个项目的列表,这也将是一个昂贵的搜索,而且我会反复计算它。我想找到一种利用DP优势的方法。