我对背包问题有一个变体，我正在努力寻找有效的解决方案。
假设您有多组项目。每个组可以有任意数量的物品，每个物品都有一个值和重量。问题是找到总价值最大、重量小于某个限制的一组项目，并且（棘手的部分）只有包含每个组中的一个项目的集合才是有效的。
也就是说，想象一下你有数百种物品可供选择，但你必须带一份三明治、一份饮料、一份零食、一只手电筒等。不仅你不能从任何一组中拿走多于一件，而且你必须至少拿走一件。如果有 g 个组，那么一天结束时总共会得到 g 个项目。
看起来这应该比基本问题更快，因为很多组合都是无效的，但我正在努力寻找解决方案。