01背包专业化 [英] 01 Knapsack specialization

问题描述

原谅我，如果这已经已经回答了，但我没有算法有深入的了解，并不总是发现的算法不同专业之间的微妙之处。我有（我认为是）的01-背包问题的轻微变种。我有一个背包，有最大权重W，而且有N个项目从选择具有重量W和价值诉我想要做的就是最大化的总价值，V，而不超过W.

Excuse me if this has been answered already, but I don't have a deep knowledge of algorithms and don't always notice the subtleties between different specializations of the algorithms. I have (what I think is) a slight variant of the 01-Knapsack problem. I have a knapsack that has max weight W, and there are N items to choose from that have a weight w and value v. What I want to do is maximize the total value, V, without going over W.

经典背包。

这里的扭曲：该项目中，我需要确保我有一定数量（不先进，但 确切的量）从不同的类别采取。

Here's the twist: Of the items, I need to make sure that I have certain amounts (not up-to, but exact amounts) taken from different categories.

所以让我们假设我们有类

So lets assume that we have categories

• F - 食品项目
• T - 玩具
• ç - 服装
• 米 - 杂项（F，T或C）

我会在2天的行程，所以我需要2食品，1玩具逗孩子，和2项的衣服。而作为一个踢球，我可以带一件其他项目要么是一架F，T或C.注意，每一个项目都是独特的，只能包括一次。

I'm going on a 2 day trip, so I need to take 2 Food items, 1 toy to amuse the kid, and 2 items of clothes. And as a kicker, I can take one additional item that is either a F, T OR C. Note that every item is unique and can be included only once.

这是所有交易算法我发现了，好像它是01（独特的项目）的混合和有界变型，但在经典界背包，我们都具有约束力的次数，我们可以包括特定项目VS一个特定的类

From all of algos I've found, it seems like it's a hybrid of the 01 (unique items) and the bounded variant, though in the classic bounded knapsack we are binding the number of times we can include a particular item vs a particular category

如果有人可以点我正确的算法会大大AP preciated。积分为code。在正常的语言，加分，如果实现允许我以查看顶n个最好的结果（你知道，万一最佳的解决方案包括玩具，我只是REALY不能站立或有2个服装是相互冲突）。

If someone could point me to the right algorithm that'd be greatly appreciated. Bonus points for code in a "normal" language, and extra points if the implementation allows me to view the top n-number best results (you know, in case the optimal solution includes the toy that I just REALY can't stand or has 2 outfits that clash with each other).

编辑：请注意，我希望能够去长途旅行，最终，因此我期待在服用8-10项总计和类别最多可以有250个左右的项目（即孩子有太多的玩具）。我可以做一些优化，减少的部分的每个类别中的项目（我真的不打算采取丑陋的夏威夷衬衫），但我不能减少它足以令直蛮力实施可行的。

Note that I want to be able to go on longer trips eventually, so I'm looking at taking 8-10 items total and the categories can have up to 250 or so items (that kid has way too many toys). I can do some optimizations to reduce some of the items in each category (I'm really not going to take the ugly hawaiian shirt), but I can't reduce it enough to make a straight brute force implementation feasible.

推荐答案

一个可能的ILP / LP配方（最明显的，但有永远只有一个制剂），可能是：（未测试）

One possible ILP/LP formulation (the most obvious one, but there's never just one formulation), could be: (not tested)

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 [电流] 的值， W [I] 的权重， F [I] 是foodness的项目， T [I] 是toyness和现在你知道什么是 C [I] 会。落入多个类别的项目数的两倍或三倍（即，如果你采取一种可食用的玩具，这将计入玩具和向食品），它可避免把该项目一的多个副本，每个其类别，那里的副本只有一个类别中的每个。

Where v[i] are values, w[i] are weights, f[i] are the "foodness" of items, t[i] are the "toyness" and by now you know what c[i] will be. Items that fall into more than one category count double or triple (ie if you take an edible toy, it will count towards the toys and towards the food items), which can be avoided by putting in multiple copies of that item, one for each of its categories, where the copies are in only one category each.

但现在真正的问题，怎么能解决呢？这仍然是一个活跃的研究领域，但这里的，应该很好地工作在这种情况下的想法。

But now the real question, how can it be solved? That's still an area of active research, but here's an idea that should work well in this case.

使用分支定界。使用线性松弛绑定（解线性规划上述问题，使决策变量 X [I] 是分数），这应该，对于这个问题，给出一个pretty的体面界（与受理，它总是给有客观价值，如果你已经解决了ILP的问题，至少是一样高的解决方案）。分支上的变量，它是不是一个整数。

With branch and bound. Bound using the linear relaxation (solve the above problem with linear programming, allowing the decision variables x[i] to be fractions), which should, for this problem, give a pretty decent bound (and admissible, it will always give a solution with an objective value that is at least as high as if you had solved an ILP problem). Branch on a variable that is not an integer.

这篇关于01背包专业化的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！