如何计算由 m 个对象组成的最大组合，每个对象都有 n 个备选方案？
How to compute the maximum combination that is composed from amongst m objects, each having n alternatives?
假设有m个对象，每个对象都有n种备选方案，每个备选方案都有一个值和一个权重。不同的对象有不同的选择。最后的objective就是select每个对象一个备选，以求组合的总价值最大化。这种组合受到不超过给定常数的排列的总权重的约束。你是怎么做到的？
关于备选方案，函数f(weight) = value of the value and weight是一个单调递增的函数，虽然确切的函数未知。对于不同的对象，此函数 f 可能相同或不同（未知）。
据我所知，如果以严格的 CS 方式求解，这应该需要 O(n^m)。这对于 m > 70 和 n > 50 尤其巨大。
然而，这是一个现实世界的工程问题，可以用一定程度的准确性换取更快的 运行 时间。我一直在考虑的一个替代方案是尝试使用学习模型来近似每个对象的备选方案的功能。一旦我们得到 f'，我们就把这些函数放在一个数学方程中，得到下面的计算问题。然后我们使用拉格朗日乘数来解决以下问题：-
我现在的解决方案是错误的吗？我是不是想得太多了，现在有更简单的解决方案吗？你会以不同的方式解决这个问题吗？是否可以将特殊的数据结构与我的方法结合使用以使其更快？
如果您乐于缩放和舍入权重以使它们成为小整数，将会有动态规划解决方案。
在这样做之后创建一个table，对于每个 i 和每个权重 w，table[i][w] = 使用前 i 个对象可以实现的最大值并且总重量最多为 w.
您可以根据 i=n 的结果计算出 i=n+1 的结果 - 只需考虑第 n+1 个对象的所有可能选择，然后查看前 n 个对象的最佳答案。
还要保留足够的簿记，例如 i 和 n 的每个组合的最佳选择，这样当您使用所有对象和实际重量约束计算出可能的最佳值时，您可以追溯到找到正确的答案（实际上在这种情况下，如果你保持 table 的权重，我认为你可以很容易地回溯而无需保留额外的笔记）。
这样做的成本是对象数量乘以每个对象的选择数量再乘以最大总权重 - 因此您可以看到在获得具有精细划分和大总权重的准确答案与快速答案之间存在权衡具有粗略的划分和较小的总权重，在四舍五入权重之前除以一个大数。
在我看来，这是一个非常适合抛给混合整数规划 (MIP) 求解器的问题。 MIP 模型可能如下所示：
一些注意事项：
- 这不完全是背包问题，因为我们有两个约束（背包问题通常只处理一个约束）。
- 当模型包含离散变量时，拉格朗日乘子的方法通常不适用。在我的模型中 x 是一个二元变量，即它只能假设值为零或一。
- 我不假设某些将权重映射到值的函数。我只是假设您有每个 object/alternative 的重量和价值数据。 （如果你有一个函数来计算给定权重的值，你可以应用该函数来预先计算值；即在我们解决问题之前）。
假设有m个对象，每个对象都有n种备选方案，每个备选方案都有一个值和一个权重。不同的对象有不同的选择。最后的objective就是select每个对象一个备选，以求组合的总价值最大化。这种组合受到不超过给定常数的排列的总权重的约束。你是怎么做到的？
关于备选方案，函数f(weight) = value of the value and weight是一个单调递增的函数，虽然确切的函数未知。对于不同的对象，此函数 f 可能相同或不同（未知）。
据我所知，如果以严格的 CS 方式求解，这应该需要 O(n^m)。这对于 m > 70 和 n > 50 尤其巨大。
然而，这是一个现实世界的工程问题，可以用一定程度的准确性换取更快的 运行 时间。我一直在考虑的一个替代方案是尝试使用学习模型来近似每个对象的备选方案的功能。一旦我们得到 f'，我们就把这些函数放在一个数学方程中，得到下面的计算问题。然后我们使用拉格朗日乘数来解决以下问题：-
我现在的解决方案是错误的吗？我是不是想得太多了，现在有更简单的解决方案吗？你会以不同的方式解决这个问题吗？是否可以将特殊的数据结构与我的方法结合使用以使其更快？
如果您乐于缩放和舍入权重以使它们成为小整数，将会有动态规划解决方案。
在这样做之后创建一个table，对于每个 i 和每个权重 w，table[i][w] = 使用前 i 个对象可以实现的最大值并且总重量最多为 w.
您可以根据 i=n 的结果计算出 i=n+1 的结果 - 只需考虑第 n+1 个对象的所有可能选择，然后查看前 n 个对象的最佳答案。
还要保留足够的簿记，例如 i 和 n 的每个组合的最佳选择，这样当您使用所有对象和实际重量约束计算出可能的最佳值时，您可以追溯到找到正确的答案（实际上在这种情况下，如果你保持 table 的权重，我认为你可以很容易地回溯而无需保留额外的笔记）。
这样做的成本是对象数量乘以每个对象的选择数量再乘以最大总权重 - 因此您可以看到在获得具有精细划分和大总权重的准确答案与快速答案之间存在权衡具有粗略的划分和较小的总权重，在四舍五入权重之前除以一个大数。
在我看来，这是一个非常适合抛给混合整数规划 (MIP) 求解器的问题。 MIP 模型可能如下所示：
一些注意事项：
- 这不完全是背包问题，因为我们有两个约束（背包问题通常只处理一个约束）。
- 当模型包含离散变量时，拉格朗日乘子的方法通常不适用。在我的模型中 x 是一个二元变量，即它只能假设值为零或一。
- 我不假设某些将权重映射到值的函数。我只是假设您有每个 object/alternative 的重量和价值数据。 （如果你有一个函数来计算给定权重的值，你可以应用该函数来预先计算值；即在我们解决问题之前）。