整数分区的JavaScript递归实现
整数分区的JavaScript递归实现
提问于 2015-12-15 20:30:23
问题：不重排的整数划分
输入：非负数的排列S {s1，。。。，sn}和整数k。
Output：将S划分为k或更少范围的最大任务，以最小化所有范围上的最大和，而无需重新排序任何数字。
示例input = [100, 200, 300, 400, 500, 600, 700, 800, 900]应该输出最大的作业，该作业只有1,700，因为数组最好是分区( 100 200 300 400 500 | 600 700 | 800 900 )。
我的功能不起作用了。例如，当输出1,700时，它输出了2,400。不知道出了什么问题。
我的密码
var integerPartitionRec = function(n, k, S) {
function sum(p, c) {
return p + c;
}
if (i === 1) return S[1];
if (k === 1) return S.slice(0, n).reduce(sum);
var cost, min_cost = Number.MAX_VALUE;
for (var i = 1; i < n; i++) {
cost = Math.max(integerPartitionRec(i, k - 1, S), S.slice(i).reduce(sum));
min_cost = Math.min(min_cost, cost);
}
return min_cost;
};
var run = function() {
var test = [100, 200, 300, 400, 500, 600, 700, 800, 900];
console.log(integerPartitionRec(test.length, 3, test));
};
run();回答 2
Stack Overflow用户
回答已采纳
发布于 2015-12-15 21:19:14
如果我理解你的算法：
- 如果
n == 1有一个大小为1的数组，不能拆分，那么最优的解决方案是不拆分，并返回元素的值，该值也是整个数组的总和：S[0](您不正确地放置S[1]) - 如果
k == 1不能再拆分，那么返回整个数组的和 - 否则，尝试在任何可能的位置拆分(除了最开始的
i=0和最后面的i=n，因为这些是假的分裂，如果您可以这样做总是更好)，检查结果，并采取最好的分割。
但是在递归调用中，您应该只考虑直到n的数组，而在代码中，在这一行中：
cost = Math.max(integerPartitionRec(i, k - 1, S), S.slice(i).reduce(sum));考虑整个数组，因为从i到数组末尾的S.slice(i).reduce(sum)和，即使从n到末尾已经在上一次调用的“尾”中计算了，所以您考虑了两次！
你可以通过让片停在n上来解决问题
cost = Math.max(integerPartitionRec(i, k - 1, S), S.slice(i, n).reduce(sum));或者，只需将拆分的第一部分传递给递归调用，就可以完全避免使用n：
var integerPartitionRec = function(k, S) {
function sum(p, c) {
return p + c;
}
if (k === 1 || S.length === 1) return S.reduce(sum);
var cost, min_cost = Number.MAX_VALUE;
for (var i = 1; i < S.length; i++) {
cost = Math.max(integerPartitionRec(k - 1, S.slice(0, i)), S.slice(i).reduce(sum));
min_cost = Math.min(min_cost, cost);
}
return min_cost;
};Stack Overflow用户
发布于 2015-12-15 21:05:44
我做了一些随机的改变，它现在打印1700年
var integerPartitionRec = function(n, k, S) {
function sum(p, c) {
return p + c;
}
if (n === 1) return S[1];
if (k === 1) return S.slice(0, n).reduce(sum);
var cost, min_cost = Number.MAX_VALUE;
for (var i = 1; i < n; i++) {
cost = Math.max(integerPartitionRec(i, k - 1, S), S.slice(i, n).reduce(sum));
min_cost = Math.min(min_cost, cost);
}
return min_cost;
};
var run = function() {
var test = [100, 200, 300, 400, 500, 600, 700, 800, 900];
console.log(integerPartitionRec(test.length, 3, test));
};
run();但我宁愿使用另一种算法:您可以对答案使用二进制搜索，然后在O(n)中检查是否可以将数组划分为k部分，其中每个部分都小于某个常量。它将是O(n log sum)而不是O(n^2)
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/34298823
复制相关文章
相似问题
腾讯云开发者
