从不同群体中挑选的背包

Question

我有一个关于背包问题的变体，我正在努力寻找有效的解决方案。

假设您有多组项目。每个组可以有任意数量的项目，每个项目都有一个值和权重。问题是找到总价值最大、重量 < 某个限制的项目集，并且（棘手的部分）只有包含每组中的一个项目的集合才有效。

也就是说，假设您有数百件物品可供挑选，但您必须拿走一个三明治、一份饮料、一份零食、一个手电筒等。不仅如此，您不能从任何一组中拿取超过一件, 但如果有 g 个组，那么你必须在一天结束时得到恰好 g 个项目。

看起来这应该比基本问题做起来更快，因为很多组合都是无效的，但我正在努力寻找解决方案。

Answer 1

对于整数权重和不太大的限制，您可以应用通常的动态规划方法（稍作修改）。

使用一对数组将每个可能的权重映射到值。这些数组之一 (A) 保存那些已处理的组的结果。其他数组 (B) 用于从第一个数组和当前正在处理的组的项目中接收值的总和。当从一组到另一组时，交换这些数组并清除数组 B。最后（像往常一样）您必须从数组 B.

中获取最大值

渐近复杂度与通常的动态规划算法相同。但是你的结论 should be faster to do than the basic problem 在某种程度上是正确的，因为你可以相互独立地处理同一组的每个元素，所以这种对通常算法的修改可以更好地并行化。

Answer 2

C++ 示例代码。函数 returns 最大可实现值，或 -1 如果不存在可行的解决方案。它在 O(n * max_weight) 中运行，其中 n 是计算所有组的项目总数，max_weight 是重量限制。复杂度本质上与解决原始背包问题的经典算法相同。该代码实现了 Evgeny Kluev 的答案中的算法。

int CalcMaxValue(const std::vector<std::vector<int>>& weight,
                 const std::vector<std::vector<int>>& value,
                 int max_weight) {
    std::vector<int> last(max_weight + 1, -1);
    if (weight.empty()) return 0;
    for (int i = 0; i < weight[0].size(); ++i) {
        if (weight[0][i] > max_weight) continue;
        last[weight[0][i]] = std::max(last[weight[0][i]], value[0][i]);
    }
    std::vector<int> current(max_weight + 1);
    for (int i = 1; i < weight.size(); ++i) {
        std::fill(current.begin(), current.end(), -1);
        for (int j = 0; j < weight[i].size(); ++j) {
            for (int k = weight[i][j]; k <= max_weight; ++k) {
                if (last[k - weight[i][j]] < 0) continue;
                current[k] = std::max(current[k], last[k - weight[i][j]] + value[i][j]);
            }
        }
        std::swap(current, last);
    }    
    return *std::max_element(last.begin(), last.end());
}

从不同群体中挑选的背包

Knapsack with selection from distinct groups

algorithm

knapsack-problem