我们有：
var range = [9,18,3,14,2,6,12,7,11,2,1,4]
var total = 89;
var group_size = total / 3;
至于结果，我需要3组大小相似，但Group1和Group2不能超过GROUP_SIZE更大。
这个例子的结果将是
var group1 = 27; // 9,18
var group2 = 25; // 3,14,2,6
var group3 = 37; // 12,7,11,2,1,4
我怎样才能在Javascript / jQuery的实现这一目标？
我认为你需要，如果你想这样的JavaScript弹出值。 就像是：
var range = [9,18,3,14,2,6,12,7,11,2,1,4]
var total = 89;
var group_size = total / 3;
var values = [0];
var groupnr = 0;
// Reverse the array, because pop will get the last element
range = range.reverse();
// While elements
while( range.length ) {
// get the last element and remove from array
var curvalue = range.pop();
// To large, create a new element
if( values[groupnr] + curvalue > group_size && groupnr < 2 ) {
groupnr++;
values[groupnr] = 0;
}
// Increase
values[groupnr] += curvalue;
}
console.log(values);
更新 ：这确实解决了类似的问题（由作者自删除），这不包括前两组不能超过平均值的限制。 随着这一限制，这是一个更简单的问题，一个可能不会引起我的注意。 我在这里留下我的答案，因为它回答了这个问题似乎是算法有意思。
我必须使用一个答案Ramda函数式编程库 。 你可以看到它在行动的jsfiddle 。 （见下文对这个不取决于Ramda的更新版本。）Ramda提供了许多便捷的功能，使代码更简单。 如果你在所有使用函数式编程，但如果你已经习惯了类似的工具他们都不应该奇怪下划线或LoDash参数订单可能会向后似乎。 （相信我，有一个很好的理由。）
var equalSplit = (function() {
var square = function(x) {return x * x;};
var variance = function(groups) {
var sizes = map(sum, groups),
mean = sum(sizes) / sizes.length;
return sum(map(pipe(subtract(mean), square), sizes));
};
var firstGroupChoices = function(group, count) {
if (group.length < 2 || count < 2) {return group;}
var mean = sum(group) / count;
var current = 0, next = group[0], idx = 0;
do {
current = next;
next = next + group[++idx];
} while (next < mean);
if (next === mean) {
return [group.slice(0, idx + 1)]
} else {
return [
group.slice(0, idx),
group.slice(0, idx + 1)
];
}
};
var val = function(group, count, soFar) {
if (count <= 0 || group.length == 0) {
return {groups: soFar, variance: variance(soFar)};
}
if (count == 1) {
return val([], 0, soFar.concat([group]));
}
var choices = firstGroupChoices(group, count);
var values = map(function(choice){
return val(group.slice(choice.length), count - 1,
soFar.concat([choice]));
}, choices);
return minWith(function(a, b) {
return a.variance - b.variance;
}, values);
};
return function(group, count) {
return val(group, count, []).groups;
}
}());
下面是从小提琴的一些示例输出：
==================================================
Input: [9,18,3,14,2,6,12,7,11,2,1,4]
Split into 3 groups
--------------------------------------------------
Groups: [[9,18,3],[14,2,6,12],[7,11,2,1,4]]
Totals: [30,34,25]
Variance: 40.66666666666667
==================================================
==================================================
Input: [9,18,3,2,6,12,11,2,4]
Split into 3 groups
--------------------------------------------------
Groups: [[9,18],[3,2,6,12],[11,2,4]]
Totals: [27,23,17]
Variance: 50.66666666666667
==================================================
==================================================
Input: [23,10,6,22,22,21,22,14,16,21,13,14,22,16,22,6,16,14,8,20,10,19,12,14,12]
Split into 5 groups
--------------------------------------------------
Groups: [[23,10,6,22,22],[21,22,14,16],[21,13,14,22],[16,22,6,16,14,8],
[20,10,19,12,14,12]]
Totals: [83,73,70,82,87]
Variance: 206
==================================================
我并不相信这个算法会给你一个实际的最佳解决方案。 我认为有一些机会，一个搜索可能陷入局部极小，并在搜索空间的附近的山谷没有注意到全球最低。 但我还没有很努力要么证明它还是拿出了一个反例。 也有一个合理的机会，它实际上是正确的。 我不知道如果有一些更高效的算法莫过于此。 问题隐约感觉就像分割的问题和背包问题，但我知道我从来没有穿过它之前运行。 许多这些问题是NP硬/ NP完成的，所以我不希望这有一个可用的真正有效的算法。
在一个相当简单的递归的方式这一个工程。 内部val函数接受的数字阵列，组创建的数量，和与蓄压器（ soFar包含已经创建至今的所有组）。 如果count为零，则返回基于累加器的简单结果。 如果count为1时，用空复发group ，一个count的零，一蓄能器，现在包括原始group作为其最后一个元素。
对于任何其他值count它计算剩余的组的平均大小，然后选择该组比平均更小和比它更大的第一一个（具有一种特殊情况的最后初始部分和如果存在的话正好等于它），浮现于找到的值，如果这些部分序列被用作在雁组，然后返回一个具有较小的值。
被确定的值通过下式计算的方差中形成的每个子组的总值。 方差是与平均值的距离的平方和。
举例来说，如果你开始使用这些值：
[8, 6, 7, 5, 3, 1, 9]
并希望将其分为三组，你将有一个平均
(8 + 6 + 7 + 5 + 3 + 1 + 9 = 39) / 3 => 13
如果分手起来是这样的：
[[8, 6], [7, 5, 3], [1, 9]]
你将有总计
[14, 15, 10]
和方差
(14 - 13)^2 + (15 - 13)^2 + (10 - 13)^2 => 14
但是，如果你打破了他们这样的：
[[8, 6], [7, 5], [3, 1, 9]]
你的总数将是
[14, 12, 13]
和你的差异会
[14 - 13)^2 + (12 - 13)^2 + (13 - 13)^2 => 2
而且，由于后者拆分具有较低的方差它被认为是更好的。
equalSplit([9, 18, 3, 2, 6, 12, 11, 2, 4], 3 []) = minVal(
equalSplit([18, 3, 2, 6, 12, 11, 2, 4], 2, [[9]]),
equalSplit([3, 2, 6, 12, 11, 2, 4], 2, [[9, 18]])
);
equalSplit([18, 3, 2, 6, 12, 11, 2, 4], 2, [[9]]) =
equalSplit([12, 11, 2, 4], 1, [[9], [18, 3, 2, 6]]);
equalSplit([3, 2, 6, 12, 11, 2, 4], 2, [9, 18]) = minVal(
equalSplit([12, 11, 2, 4], 1, [[9, 18], [3, 2, 6]])
equalSplit([11, 2, 4], 1, [[9, 18], [3, 2, 6, 12]]
);
equalSplit([12, 11, 2, 4], 1, [[9], [18, 3, 2, 6]]) =
equalSplit([], 0, [[9], [18, 3, 2, 6], [12, 11, 2, 4]])
equalSplit([12, 11, 2, 4], 1, [[9, 18], [3, 2, 6]]) =
equalSplit([], 0, [[9, 18], [3, 2, 6], [12, 11, 2, 4]]) =
equalSplit([11, 2, 4], 1, [[9, 18], [3, 2, 6, 12]]
equalSplit([], 0, [[9, 18], [3, 2, 6, 12], [11, 2, 4]]
equalSplit([], 0, [[9], [18, 3, 2, 6], [12, 11, 2, 4]]) =
variance((9), (18 + 3 + 2 + 6), (12 + 11 + 2 + 4)) =
variance(9, 29, 29) = 266.67
equalSplit([], 0, [[9, 18], [3, 2, 6], [12, 11, 2, 4]]) =
variance((9 + 18), (3 + 2 + 6), (12 + 11 + 2 + 4)) =
variance(27, 11, 29) = 194.67
equalSplit([], 0, [[9, 18], [3, 2, 6, 12], [11, 2, 4]] =
variance((9 + 18), (3 + 2 + 6 + 12), (11 + 2 + 4)) =
variance(27, 23, 17) = 50.67
目前几乎可以肯定是很多可以做清理该代码。 但也许它至少对你的问题的开始。 这是一个非常有趣的挑战。
我确实创造了一个版本，它不依赖于Ramda。 该代码是非常相似的。 （我想我真的不需要Ramda，至少不是最终版本。）：
var equalSplit = (function() {
var sum = function(list) {return list.reduce(function(a, b) {
return a + b;
}, 0);};
var square = function(x) {return x * x;};
var variance = function(groups) {
var sizes = groups.map(sum),
mean = sum(sizes) / sizes.length;
return sum(sizes.map(function(size) {
return square(size - mean);
}, sizes));
};
var firstGroupChoices = function(group, count) {
if (group.length < 2 || count < 2) {return group;}
var mean = sum(group) / count;
var current = 0, next = group[0], idx = 0;
do {
current = next;
next = next + group[++idx];
} while (next < mean);
if (next === mean) {
return [group.slice(0, idx + 1)]
} else {
return [
group.slice(0, idx),
group.slice(0, idx + 1)
];
}
};
var val = function(group, count, soFar) {
if (count <= 0 || group.length == 0) {
return {groups: soFar, variance: variance(soFar)};
}
if (count == 1) {
return val([], 0, soFar.concat([group]));
}
var choices = firstGroupChoices(group, count);
var values = choices.map(function(choice){
return val(group.slice(choice.length), count - 1,
soFar.concat([choice]));
});
return values.sort(function(a, b) {
return a.variance - b.variance;
})[0];
};
return function(group, count) {
return val(group, count, []).groups;
}
}());
当然，现在在上面提到的，这比回答现在正在问一个稍微不同的问题，但我认为这是一个更有趣的问题！ :-)
