抱歉，如果这个问题已经得到解答，但我对算法没有深入的了解，并且并不总是注意到算法不同专业之间的微妙之处。我有（我认为是）01-背包问题的一个轻微变体。我有一个背包，其最大重量为 W，有 N 个重量为 w、价值为 v 的物品可供选择。我想要做的是最大化总价值 V，而不超过 W。
经典背包。
这是转折：在这些物品中，我需要确保我有一定的数量（不是最多的，但是exact数量）取自不同类别。
所以我们假设我们有类别
- F - 食品
- T - Toys
- C - 衣服
- M - 其他（F、T 或 C）
我要去 2 天的旅行，所以我需要带 2 份食物、1 个供孩子娱乐的玩具和 2 件衣服。作为一个补充，我可以额外选择一个 F、T 或 C 项目。请注意，每个项目都是唯一的，并且只能包含一次。
从我发现的所有算法来看，它似乎是 01（独特物品）和有界变体的混合体，尽管在经典的有界背包中，我们绑定了可以包含特定物品与特定物品的次数category
如果有人能给我指出正确的算法，我将不胜感激。使用“正常”语言编写的代码可以获得加分，如果实现允许我查看前 n 个最佳结果，则可以获得额外加分（你知道，如果最佳解决方案包括我真的无法忍受或拥有的玩具） 2 套相互冲突的服装）。
编辑：请注意，我希望最终能够进行更长的旅行，因此我考虑总共携带 8-10 件物品，并且类别最多可以包含 250 件左右的物品（那个孩子的玩具太多了）。我可以做一些优化来减少some每个类别中的项目的数量（我真的不会选择丑陋的夏威夷衬衫），但我无法将其减少到足以使直接暴力实施变得可行。
一种可能的 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
Where v[i]是价值观，w[i]是权重，f[i]是物品的“善”，t[i]是“玩具”，现在你知道是什么了c[i]将。属于多个类别的物品计数为两倍或三倍（即，如果您拿走一个可食用玩具，它将计入玩具和食品），可以通过放入该物品的多个副本（每个副本一个）来避免这种情况其类别，其中每个副本仅属于一个类别。
但现在真正的问题是，如何解决？这仍然是一个活跃的研究领域，但这里有一个在这种情况下应该行之有效的想法。
有分支定界。使用线性松弛有界（用线性规划解决上述问题，允许决策变量x[i]是分数），对于这个问题，它应该给出一个相当不错的界限（并且可以接受，它总是会给出一个具有至少与解决 ILP 问题一样高的目标值的解决方案）。对非整数变量进行分支。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
