Knapsack with selection from distinct groups

Question

I have a variation on the Knapsack Problem that I'm struggling to find an efficient solution for.

Let's say you have multiple groups of items. Each group can have an arbitrary number of items, each with a value and weight. The problem is to find the set of items with maximum total value, weight < some limit, and (the tricky part) only sets than include one item from EVERY group are valid.

That is, imagine you have hundreds of items to pick from, but you must take one sandwich, one beverage, one snack, one flashlight, etc. Not just that you can't take more than one from any group, but you must at the end of the day end up with exactly g total items if there are g groups.

It seems like this should be faster to do than the basic problem, because so many combinations are invalid, but I'm struggling to find a solution.

Your problem seems flawed. What if the requirements of selecting exactly g items and weight limit conflict? — Lingxi
An easy (yet exponential in the number of "groups") solution is to add boolean dimension for each group that indicates if an item was chosen or not from this set. — amit
@Lingxi - excellent point. Let's assume we know (as we could easily confirm ahead of time) that at least one solution exists. — Dov Rosenberg
@amit - So simply skip over items that are in already used groups? Wouldn't that risk both creating a suboptimal answer and creating an answer where not every group was represented? — Dov Rosenberg

Lingxi Lingxi · Accepted Answer · 2015-04-19T17:30:51

Example code in C++. The function returns the maximum achievable value, or -1 if no feasible solutions exist. It runs in O(n * max_weight) where n is the total number of items counting all groups, and max_weight is the weight limit. The complexity is essential the same as the classic algorithm that solves the original knapsack problem. The code implements the algorithm in Evgeny Kluev's answer.

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

2 Answers