algorithm - 01 背包特化

Question

对不起，如果这个问题已经得到解答，但我对算法的了解不深，并不总是注意到算法不同特化之间的微妙之处。我有(我认为是)01-Knapsack 问题的轻微变体。我有一个最大重量为 W 的背包，有 N 件元素可供选择，重量为 w，值(value)为 v。我想要做的是最大化总值(value) V，而不超过 W。

经典背包。

这里有一个转折点:在这些项目中，我需要确保我有一定数量(不是最多，但准确金额)取自不同类别。

所以让我们假设我们有类别

• F - 食品
• T - 玩具
• C - 衣服
• M - 杂项(F、T 或 C)

我要进行为期 2 天的旅行，所以我需要带 2 件食物、1 件给 child 逗乐的玩具和 2 件衣服。作为一个 kicker，我可以再拿一个 F、T 或 C 的项目。请注意，每个项目都是独一无二的，并且只能包含一次。

从我发现的所有算法来看，它似乎是 01(独特元素)和有界变体的混合体，尽管在经典的有界背包中我们绑定(bind)了我们可以包含特定元素的次数与特定的类别

如果有人能指出正确的算法，我将不胜感激。使用“正常”语言编写代码的奖励积分，如果实现允许我查看前 n 个最佳结果，则额外加分(你知道，以防最佳解决方案包括我真的无法忍受或拥有的玩具2 套相互冲突的服装)。

编辑:请注意，我希望最终能够进行更长的旅行，所以我打算总共带 8-10 件元素，类别最多可以有 250 件左右的元素(那个 child 的玩具太多了).我可以做一些优化来减少每个类别中的一些项目(我真的不会拿那件丑陋的夏威夷衬衫)，但我不能将它减少到足以产生直接蛮力实现可行。

Answer 1

一种可能的 ILP/LP 公式(最明显的公式，但绝不会只有一种公式)可能是:(未测试)

maximize sum(v[i] * x[i])
subject to:
0 <= x[i] <= 1        // can take every item at most once
sum(w[i] * x[i]) <= W // don't go over the weight limit
F <= sum(f[i] * x[i]) <= F + 1 // take F or F+1 food items
T <= sum(t[i] * x[i]) <= T + 1 // take T or T+1 toys
C <= sum(c[i] * x[i]) <= C + 1 // take C or C+1 clothes
sum(x[i]) == F + T + C + M     // take exactly the right number of items

其中v[i]是值，w[i]是权重，f[i]是项目的“食物” , t[i] 是“玩具”，现在您知道 c[i] 是什么了。属于一个以上类别的元素计数两倍或三倍(即，如果您拿了一个可食用的玩具，它将计入玩具和食品)，可以通过放入该元素的多个副本来避免这种情况，每个副本一个它的类别，其中每个副本仅属于一个类别。

但现在真正的问题是，如何解决呢？这仍然是一个活跃的研究领域，但这里有一个想法应该适用于这种情况。

使用分支定界法。使用线性松弛限制(用线性规划解决上述问题，允许决策变量 x[i] 为分数)，对于这个问题，它应该给出一个相当不错的界限(并且可以接受，它总是会给出一个客观值(value)至少与解决 ILP 问题一样高的解决方案)。在不是整数的变量上分支。