algorithm - 加权箱包装/背包优化

Question

我正在努力对我正在处理的问题进行分类，这意味着我无法弄清楚是否有任何既定的启发式解决方案。您认为这是什么问题，您建议我如何解决它？

I have a series of buckets A, B, C, D. Each one can contain a certain number of items. The total size of the buckets matches the size of the population. The items in the population each have a score for A, B, C, D.

I want to sort the items into the buckets such that the total score for matching buckets is maximised; i.e. the A scores for all the items in bucket A, the B scores for all the items in bucket B and so on. It follows that it is possible for an item to ideally be in bucket B even if its A score is higher, as there might be many items with high A scores and few with high B scores.

Answer 1

这看起来像 minimum-cost maximum flow问题。它确实是最大成本，但可以通过取消权重来修改。

考虑以下网络。有一个来源，s ，和一个水槽，t .

每个项目 i由顶点 u_i 表示, 有边 s -> u_i容量为 1，成本为 0。

每个桶也由一个顶点表示:v_A v_B ， 等等。有边v_A -> t容量为组 A 的大小且成本为 0，其他组的边类似。

最后，还有边 u_i -> v_G其容量为 1，成本等于(减去将项目 i 放入组 G 的得分)。

观察该网络中的任何最大流都对应于将项目划分为组，以便每个组都具有给定的大小。

观察这个网络中最小成本最大流是一个分区，其中该分区的总分最大化。

这与项目数量和组数量成比例。此外，这很容易扩展到组的大小可以变化到一定限度的情况，但每个项目仍必须属于一个组。