有界背包算法返回的几种组合
Several combination returned by bounded Knapsack algorithm
此任务类似于有界背包问题 (BKP)。
我们有大约 300 种不同的餐食，参数如下：ID、价格、importance/rating、类别。
例如：
id price importance type
-----------------------------
1 100 78 butter
2 50 89 milk
3 70 66 milk
4 66 50 butter
我们想要selectTOP-10最佳产品组合，但是具体配置，我们只想拿3种黄油，2种面包和2种牛奶。这 TOP-10 组合必须具有最高的重要性。
我们还必须考虑可用预算。
这与背包问题有点不同，因为这里我们想要的是 TOP-10 的结果，而不仅仅是最好的。
并且同一组（例如黄油）中的每个 meal/product 都有不同的价格和 importance/rating。
一种可能足够的启发式方法是使用具有相当大人口的进化算法（对于背包类型的问题，它往往很容易编程），让它进化一段时间，然后取顶部10 个解决方案。
获得可证明的前 10 名解决方案当然会更难（从字面上看——这显然是 NP 难的）。一种方法是将其求解至最优，记录解，添加约束以排除该解，然后求解。重复此操作，直到获得前 10 个解决方案。
我猜价格是整数而且比较小，你正在考虑一些学校式的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)）与只找到一个最佳解决方案相比。
特殊问题
我觉得你应该用二级算法来解决你的问题：
- 运行 每个项目类别中有界背包问题的 DP。因此，您将获得 k 个类别的项目与每个总成本（以及有限数量的项目）的最佳组合。
- 找到在步骤 1 中获得的解决方案的最佳组合。必须从所考虑的每个类别中提取一个解决方案。
对于单个类别，求解 DP 以从 N 项列表中选择 s 项 W 背包大小似乎需要 O(s N W k^2) 时间。在步骤 2 中合并来自 c 类别的解决方案似乎需要 O(c W^2 k^2)，但它可以减少到 O(c W k log(W k))如果使用平衡树进行合并。
此任务类似于有界背包问题 (BKP)。 我们有大约 300 种不同的餐食，参数如下：ID、价格、importance/rating、类别。
例如：
id price importance type
-----------------------------
1 100 78 butter
2 50 89 milk
3 70 66 milk
4 66 50 butter
我们想要selectTOP-10最佳产品组合，但是具体配置，我们只想拿3种黄油，2种面包和2种牛奶。这 TOP-10 组合必须具有最高的重要性。 我们还必须考虑可用预算。
这与背包问题有点不同，因为这里我们想要的是 TOP-10 的结果，而不仅仅是最好的。 并且同一组（例如黄油）中的每个 meal/product 都有不同的价格和 importance/rating。
一种可能足够的启发式方法是使用具有相当大人口的进化算法（对于背包类型的问题，它往往很容易编程），让它进化一段时间，然后取顶部10 个解决方案。
获得可证明的前 10 名解决方案当然会更难（从字面上看——这显然是 NP 难的）。一种方法是将其求解至最优，记录解，添加约束以排除该解，然后求解。重复此操作，直到获得前 10 个解决方案。
我猜价格是整数而且比较小，你正在考虑一些学校式的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)）与只找到一个最佳解决方案相比。
特殊问题
我觉得你应该用二级算法来解决你的问题：
- 运行 每个项目类别中有界背包问题的 DP。因此，您将获得 k 个类别的项目与每个总成本（以及有限数量的项目）的最佳组合。
- 找到在步骤 1 中获得的解决方案的最佳组合。必须从所考虑的每个类别中提取一个解决方案。
对于单个类别，求解 DP 以从 N 项列表中选择 s 项 W 背包大小似乎需要 O(s N W k^2) 时间。在步骤 2 中合并来自 c 类别的解决方案似乎需要 O(c W^2 k^2)，但它可以减少到 O(c W k log(W k))如果使用平衡树进行合并。