解决与背包问题相关的问题的最佳方法是什么，背包问题有 3 个变量，例如:值(value)、重量和体积？ (取最大可能值，有最大重量和体积限制)
我试过使用定义的索引，基于它的值/(重量*体积)，但我相信这不会给我最好的解决方案，所以我搜索了一些人建议使用动态规划，但所有主题都相关为此，只有 2 个变量(值和权重)，我不知道超过 2 个变量会如何影响这一点。
最佳答案
您应该能够扩展具有一个约束的标准动态规划问题以处理两个或更多约束。
回顾一下，背包问题的标准 DP 解决方案的工作原理是按某种顺序对元素进行排序，然后回答以下形式的所有问题:
What is the maximum value that can be produced using the first i items without exceeding weight w?
这变成了一个二维表格，其中一个轴表示正在考虑的项目数量，另一个轴表示不同的可能重量值。要填写表格，您可以通过将条目设置为零来填充 i = 0 的一维条目切片(如果没有项目，则无法获得任何值)，然后通过考虑填充 i = 1 的一维切片是否包含或排除第一项，通过考虑是否包含或排除第二项等来考虑 i = 2 的切片。然后运行时间为 O(nW)，其中 n 是项目数，W 是允许的最大数量重量，因为这些是表格的尺寸，每个条目的工作量为 O(1)。
如果你现在有两个约束(重量和体积)，你可以解决以下形式的所有问题:
What is the maximum value that can be produced using the first i items without exceeding weight w or volume v?
这变成了一个 3D 表格，其中一个轴表示正在考虑的项目数量，另一个轴表示不同的可能重量值，第三个轴表示可能的体积值。要填写表格，您可以通过将条目设置为零来填充 i = 0 的条目的二维切片(如果没有项目，则无法获得任何值)，然后通过考虑填充 i = 1 的二维切片是否包含或排除第一项，i = 2的切片通过考虑是否包含或排除第二项等。运行时间为O(nWV)，其中n为项目数，W为最大允许权重, V 是最大允许体积(而不是值)，因为这是表条目的数量，并且需要 O(1) 的工作来填充每个。
您知道如何针对更多的约束条件进行调整吗？
关于algorithm - 如何用 3 个变量解决背包问题？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/56639862/