如何用 3 个变量解决背包问题？
How can I solve knapsack problems with 3 variables?
解决背包问题的最佳方法是什么，背包问题有 3 个变量，例如：价值、重量和体积？ （取最大可能值，有最大重量和体积限制）
我试过使用定义的索引，基于它的值/(重量*体积)，但我相信这不会给我最好的解决方案，所以我搜索了一些人建议使用动态规划，但所有与此相关的主题，只有 2 个变量（值和权重），我不知道超过 2 个变量会如何影响它。
您应该能够扩展具有一个约束的标准动态规划问题以处理两个或更多约束。
回顾一下，背包问题的标准 DP 解决方案是按某种顺序对物品进行排序，然后回答以下形式的所有问题：
What is the maximum value that can be produced using the first i items without exceeding weight w?
这变成了 2D table，一个轴表示正在考虑的项目数量，另一个轴表示不同的可能权重值。要填写 table，您可以通过将条目设置为零来填写 i = 0 的一维条目切片（如果没有项目，则无法获得任何值），然后填写 i 的一维切片= 1 通过考虑是否包含或排除第一项，i = 2 的切片通过考虑是否包含或排除第二项等。运行时间为 O(nW)，其中 n 是项目数，W是最大允许重量，因为这些是 table 的尺寸，并且您为每个条目做 O(1) 工作。
如果你现在有两个约束（重量和体积），你可以解决以下形式的所有问题：
What is the maximum value that can be produced using the first i items without exceeding weight w or volume v?
这变成了 3D table，其中一个轴表示正在考虑的项目数量，另一个轴表示不同的可能重量值，第三个轴表示可能的体积值。要填写 table，您可以通过将条目设置为零来填写 i = 0 的二维切片（如果没有项目，则无法获得任何值），然后填写 i 的二维切片= 1 通过考虑是否包含或排除第一项，切片 where i = 2 通过考虑是否包含或排除第二项等。运行时间为 O(nWV)，其中 n 是项目数，W 是最大允许重量，V 是最大允许体积（而不是值），因为这是 table 条目的数量，并且需要 O(1) 的工作来填充每个条目。
您知道如何针对更大数量的约束进行调整吗？
假设您将值、重量和体积作为参数，并且您想要计算在不超过最初可用的重量和体积限制的情况下您可以拥有的最大值， 使用动态规划。动态规划基于递归公式。所以这里只告诉大家递归公式，实现起来并不难
我用V表示可用的初始体积，W表示可用的初始重量。另外，我使用 volume[] 来引用保存体积的数组，类似地 weight[] 是权重数组。
因此，动态规划算法所需的 3 个参数是 (1) 您当前正在检查的项目（称之为 i), (2) 你还剩多少体积（称之为 vLeft）, (3) 你有多少体重左边（称之为 wLeft）。
为了优化您可以使用以下递归：
DP[i][vLeft][wLeft] = min(DP[i + 1][vLeft - volume[i]][wLeft - weight[i]], DP[i + 1][vLeft] [w左])
min 函数中左边的参数是我们选择项目的时候，右边的参数是我们不选择项目的时候。另外，当没有体积或重量时，以及当我到达最后一个项目时，您需要一些基本条件。
但是您的初始调用应该是这样的，其中 0 是起始索引。
ComputeAnswer(0, V, W)
解决背包问题的最佳方法是什么，背包问题有 3 个变量，例如：价值、重量和体积？ （取最大可能值，有最大重量和体积限制）
我试过使用定义的索引，基于它的值/(重量*体积)，但我相信这不会给我最好的解决方案，所以我搜索了一些人建议使用动态规划，但所有与此相关的主题，只有 2 个变量（值和权重），我不知道超过 2 个变量会如何影响它。
您应该能够扩展具有一个约束的标准动态规划问题以处理两个或更多约束。
回顾一下，背包问题的标准 DP 解决方案是按某种顺序对物品进行排序，然后回答以下形式的所有问题：
What is the maximum value that can be produced using the first i items without exceeding weight w?
这变成了 2D table，一个轴表示正在考虑的项目数量，另一个轴表示不同的可能权重值。要填写 table，您可以通过将条目设置为零来填写 i = 0 的一维条目切片（如果没有项目，则无法获得任何值），然后填写 i 的一维切片= 1 通过考虑是否包含或排除第一项，i = 2 的切片通过考虑是否包含或排除第二项等。运行时间为 O(nW)，其中 n 是项目数，W是最大允许重量，因为这些是 table 的尺寸，并且您为每个条目做 O(1) 工作。
如果你现在有两个约束（重量和体积），你可以解决以下形式的所有问题：
What is the maximum value that can be produced using the first i items without exceeding weight w or volume v?
这变成了 3D table，其中一个轴表示正在考虑的项目数量，另一个轴表示不同的可能重量值，第三个轴表示可能的体积值。要填写 table，您可以通过将条目设置为零来填写 i = 0 的二维切片（如果没有项目，则无法获得任何值），然后填写 i 的二维切片= 1 通过考虑是否包含或排除第一项，切片 where i = 2 通过考虑是否包含或排除第二项等。运行时间为 O(nWV)，其中 n 是项目数，W 是最大允许重量，V 是最大允许体积（而不是值），因为这是 table 条目的数量，并且需要 O(1) 的工作来填充每个条目。
您知道如何针对更大数量的约束进行调整吗？
假设您将值、重量和体积作为参数，并且您想要计算在不超过最初可用的重量和体积限制的情况下您可以拥有的最大值， 使用动态规划。动态规划基于递归公式。所以这里只告诉大家递归公式，实现起来并不难
我用V表示可用的初始体积，W表示可用的初始重量。另外，我使用 volume[] 来引用保存体积的数组，类似地 weight[] 是权重数组。
因此，动态规划算法所需的 3 个参数是 (1) 您当前正在检查的项目（称之为 i), (2) 你还剩多少体积（称之为 vLeft）, (3) 你有多少体重左边（称之为 wLeft）。
为了优化您可以使用以下递归：
DP[i][vLeft][wLeft] = min(DP[i + 1][vLeft - volume[i]][wLeft - weight[i]], DP[i + 1][vLeft] [w左])
min 函数中左边的参数是我们选择项目的时候，右边的参数是我们不选择项目的时候。另外，当没有体积或重量时，以及当我到达最后一个项目时，您需要一些基本条件。
但是您的初始调用应该是这样的，其中 0 是起始索引。
ComputeAnswer(0, V, W)