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.
For integer weights and not too large limit you could apply usual dynamic programming approach (slightly modified).
Use a pair of arrays that map every possible weight to value. One of these arrays (A) holds the result for those groups that are already processed. Other array (B) is used to receive sum of values from the first array and from items of the group being currently processed. When coming from one group to another, swap these arrays and clear array B. At the end (as usual) you have to get the largest value from array B.
Asymptotic complexities are the same as for usual dynamic programming algorithm. But your conclusion that this should be faster to do than the basic problem is somewhat true because you could process each element of the same group independently from each other, so this modification of usual algorithm is better parallelizable.
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());
}
