有界背包算法返回的几个组合

Question

这项任务类似于有界背包问题（BKP）。我们大约有300个不同的餐点，具有以下参数：ID、价格、重要性/评级、类别。

例如：

id  price  importance  type
-----------------------------
1   100     78         butter
2   50      89         milk
3   70      66         milk
4   66      50         butter

我们希望选择最佳的10种产品组合，但需要特定的配置。我们只需要3种黄油、2种面包和2种牛奶。这些最佳的10个组合必须具有最高的重要性总和。同时，我们必须考虑可用的预算。

与背包问题略有不同，因为我们想要的是最佳的10个结果，而不仅仅是最好的结果。同一组餐食/产品（例如黄油）的每个都有不同的价格和重要性/评级。

- Vit D

Answer 1

一个可行的启发式方法是使用进化算法（通常对背包问题编程相当容易）来解决，使用相当大的种群，让其进化一段时间，然后只取前10个解决方案。

当然，获得可证明的前10个解决方案会更困难（确切地说，这显然是NP-hard问题）。一种方法是将其解决到最优解，记录该解决方案，添加一个约束条件以排除该解决方案，然后重新解决。重复此过程，直到获得前10个解决方案。

- John Coleman

Answer 2

我假设价格是整数且相当低，您正在考虑一些学校类型的DP解决方案。

动态规划(DP)概述

在动态规划算法中，对于每个状态，我们仅存储单个最佳部分解。通常，我们不会物理存储这个部分解：只存储其成本和一些简单的回溯信息，以便稍后重构它。由于具有最优子结构性质，我们不存储状态的其他解：任何成本更高的部分解都有比最佳部分解更糟糕的延续。

为了找到问题的k个最佳解，您可以简单地为DP的每个状态存储k个最佳部分解。如果某个状态的解少于k个，则存储所有解。为什么可以放弃劣于其他k个部分解的部分解呢？因为其任何延续都会比那些k种更好的部分解的相应延续更糟糕。

在正向DP中，转移通常与平常一样进行。当你考虑某个状态时，应该迭代其所有最佳的k个部分解，并尝试以所有可能的方式继续每个部分解（例如，采取新项目或不采取）。对于每个继续，查看其状态。将继续插入到最佳部分解的排序列表中。如果结果有k+1个部分解，则删除最差的一个。

大多数情况下，你不想在DP中存储部分解本身。相反，仅为每个部分解存储总成本和回溯信息。回溯信息应足以明确确定DP中的前一个部分解。通过这种方式，可以找到最好的k个解决方案。似乎与仅查找一个最佳解决方案相比，具有k个最佳解决方案的DP解决方案需要多消耗O(k)倍的内存和O(k^2)倍的时间（或O(k log k))，用于背包问题。

特定问题

我认为你应该使用两级算法来解决问题：

1. 对于每个物品类别，运行一个有界背包问题的DP算法。结果将得到该类别中前k个物品组合，每个组合的总成本（和物品数量有界）。
2. 找到步骤1中获得的解的最优组合。必须从考虑的每个类别中选择一个解。

对于单个类别，解决从N个物品列表中选择s个物品，背包大小为W的DP问题似乎需要O(s N W k^2)的时间。在步骤2中合并来自c个类别的解似乎需要O(c W^2 k^2)，但如果使用平衡树进行合并，则可以将其减少到O(c W k log(W k))。

- stgatilov