亲爱的stackoverflow社区，
目前，我正试图解决一个优化问题，即给定一个数组的数字(整数或浮点数;非负)和一个正整数M，输出M个子集(任意合适长度)，使得子集中和最大的子集被最小化。子集中的元素可以是不连续的。
例如，给定一个数组[1,4,5,3]和一个整数M = 2期望的输出是[1,5]和[4,3]，其中最大的子集和是最小值为7。
另一个例子，给定数组[3,10,7,2]和整数M = 3，期望的输出是[3,2]、[7]和[10]，甚至是[3,7]、[2]和[10]其中最小的最高子集和为10。
有没有人经历过这样的优化?我相信这是Kadane算法的一个变种。
任何链接，伪代码，python代码等都非常感谢。
我想到了下面的方法来解决这个问题:
- 按升序排序
- 初始化M个空子集
- 在while循环中，向每个子集添加最小和最大的可用元素，直到没有更多的元素可以从父数组中选择
这可以看作是赋值问题的一个变体:
设v[i]为数据数组，j=1..M为子集。
x[i,j] ∈ {0,1}x[i,j] = 1 if value i is assigned to subset j
0 otherwise
我们的优化模型看起来像:
min z
z >= sum(i, v[i]*x[i,j]) ∀j "largest sum"
sum(j, x[i,j]) = 1 ∀i "assign each value to a subset"
x[i,j] ∈ {0,1}
这是一个线性混合整数规划问题，可以用任何MIP求解器来求解。
使用随机数据的结果:
---- 34 PARAMETER results
value sub1 sub2 sub3 sub4 sub5 sub6 sub7 sub8 sub9 sub10
i1 17.175 17.175
i2 84.327 84.327
i3 55.038 55.038
i4 30.114 30.114
i5 29.221 29.221
i6 22.405 22.405
i7 34.983 34.983
i8 85.627 85.627
i9 6.711 6.711
i10 50.021 50.021
i11 99.812 99.812
i12 57.873 57.873
i13 99.113 99.113
i14 76.225 76.225
i15 13.069 13.069
i16 63.972 63.972
i17 15.952 15.952
i18 25.008 25.008
i19 66.893 66.893
i20 43.536 43.536
i21 35.970 35.970
i22 35.144 35.144
i23 13.149 13.149
i24 15.010 15.010
i25 58.911 58.911
total 114.181 114.582 114.123 112.961 113.949 113.548 114.478 112.809 110.635 113.993
指出:
- 解决方案，一般来说，不是唯一的。
- 很容易添加一个禁止空子集的约束。(可能发生在更倾斜的数据集)。