自定义分区问题 [英] custom partition problem

问题描述

有人可以指导我如何解决这个问题。

Could some one guide me on how to solve this problem.

我们得到了一个包含k个元素的集合S。

We are given a set S with k number of elements in it.

现在我们必须将集合S分成x个子集，以使每个子集中的元素数量之差不超过1，并且每个子集的总和应尽可能接近

Now we have to divide the set S into x subsets such that the difference in number of elements in each subset is not more than 1 and the sum of each subset should be as close to each other as possible.

示例1：
{10、20、90、200、100}必须分为2个子集

Example 1: {10, 20, 90, 200, 100} has to be divided into 2 subsets

解决方案：{10,200} {20,90,100}

Solution:{10,200}{20,90,100}

总和为210和210

sum is 210 and 210

示例2：
{1，1，2，1，1，1，1，1，1，6}

Example 2: {1, 1, 2, 1, 1, 1, 1, 1, 1, 6}

解决方案：{1， 1,1,1,6} {1,2,1,1,1}

Solution:{1,1,1,1,6}{1,2,1,1,1}

总和为10和6。

推荐答案

我看到了两个阶段的可能解决方案。

I see a possible solution in two stages.

第一阶段

首先选择子集数N。
如果可能，对原始集合S进行排序。
将S中最大的N个数字按顺序分配到子集1至N。
以相反的顺序从S子集中分配N个最大的N个数字，从N到1。
重复进行直到分配所有数字。

Start by selecting the number of subsets, N. Sort the original set, S, if possible. Distribute the largest N numbers from S into subsets 1 to N in order. Distribute the next N largest numbers from S the subsets in reverse order, N to 1. Repeat until all numbers are distributed.

如果不能对S进行排序，然后将S中的每个数字分配到具有最少条目和最小总数的子集（或子集之一）中。

If you can't sort S, then distribute each number from S into the subset (or one of the subsets) with the least entries and the smallest total.

您现在应该拥有N个子集的大小彼此之间都在1之内，并且总数非常相似。

You should now have N subsets all sized within 1 of each other and with very roughly similar totals.

第二阶段

现在尝试完善您的近似解决方案。
选择最大的总子集L和最小的总子集M。选择L中的数字，该数字小于M中的数字，但相差不大，以至于不会增加两个子集之间的绝对差。交换两个数字。重复。并非所有子集对都具有可交换编号。每次交换都会使子集的大小保持不变。

Now try to refine the approximate solution you have. Pick the largest total subset, L, and the smallest total subset, M. Pick a number in L that is smaller than a number in M but not by so much as to increase the absolute difference between the two subsets. Swap the two numbers. Repeat. Not all pairs of subsets will have swappable numbers. Each swap keeps the subsets the same size.

如果您有很多时间，可以进行彻底的搜索。如果不是，那就尝试挑选一些明显的案例。我会说，如果差额没有减少，请不要交换数字；

If you have a lot of time you can do a thorough search; if not then just try to pick off a few obvious cases. I would say don't swap numbers if there is no decrease in difference; otherwise you might get an infinite loop.

一旦某些子集中至少有两个成员，就可以对阶段进行交错。

You could interleave the stages once there are at least two members in some subsets.

这篇关于自定义分区问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！