如何解决具有 3 个变量的背包问题？

Question

解决与背包问题相关的问题的最佳方法是什么？背包问题有 3 个变量，例如：价值、重量和体积？（最大可能的值，最大重量和体积限制）

我曾尝试使用定义的索引，基于其值/（权重*体积），但我相信这不会给我最好的解决方案，所以我进行了搜索，有些人建议使用动态编程，但所有与此相关的主题，只有 2 个变量（值和权重），我不知道超过 2 个变量会如何影响这一点。

Answer 1

您应该能够用一个约束扩展标准动态规划问题来处理两个或多个约束。

作为复习，背包问题的标准 DP 解决方案的工作原理是按某种顺序对项目进行排序，然后回答以下形式的所有问题：

在不超过重量 w 的情况下，使用前 i 个项目可以产生的最大值是多少？

这变成了一个 2D 表格，一个轴表示正在考虑的项目数量，另一个轴表示不同的可能重量值。要填写表格，您可以通过将 i = 0 的条目设置为零来填充条目的一维切片（如果没有项目，则无法获得任何值），然后通过考虑填充 i = 1 的一维切片是否包含或排除第一项、i = 2 的切片，通过考虑是否包含或排除第二项等。运行时间为 O(nW)，其中 n 是项目数，W 是最大允许值重量，因为这些是表格的尺寸，并且每个条目都执行 O(1) 工作。

如果你现在有两个约束（重量和体积），你可以解决以下形式的所有问题：

在不超过重量 w 或体积 v 的情况下，使用前 i 件物品可以生产的最大值是多少？

这变成了一个 3D 表格，一个轴表示正在考虑的项目数量，另一个轴表示不同的可能重量值，第三个轴表示可能的体积值。要填写表格，您可以通过将 i = 0 的条目设置为零来填充条目的 2D 切片（如果没有项目，则无法获得任何值），然后通过考虑填充 i = 1 的 2D 切片是否包含或排除第一项，i = 2 的切片，通过考虑是否包含或排除第二项等。 运行时间为 O(nWV)，其中 n 是项目数，W 是最大允许权重, V 是最大允许体积（而不是值），因为这是表条目的数量，并且需要 O(1) 工作来填充每个条目。

您是否看到如何针对大量约束进行调整？