我有一个包含一些整数值的数组,我需要得到其中的一个子集,它给我的最大和小于给定值
假设我有一个数组:
[40, 138, 29, 450]
我想得到这个数组的一个子集,最大化总和,但低于用户给定的限制,比如250。在这种情况下,它应该返回[139,40,29]<我看了一下这个问题和相关的答案,并尝试使用给出的代码,但我不太理解。无论如何,我已经尝试过了,将最小值设置为0,将最大值设置为给定的限制,但它总是返回“5”,这是不正确的,因为限制值大约为300,数组中的数字都超过50<我找不到任何可以帮助我的东西,所以我想问是否有人可以给我一些代码或伪代码来理解如何做到这一点。
这是一个蛮力解决方案。首先,我们从原始数组中获得所有可能的值组合,取它们的总和,看看哪一个能在不溢出给定最大值的情况下得到最高值。
var ary = [40, 138, 29, 450];
// Function to construct a power set. A power set is just the set of
// all possible subsets of some given set.
function makePowerSet(ary) {
powerSet = [];
for (let ps = 1; ps <= Math.pow(2, ary.length); ps++) {
subset = [];
for (let i = 0; i < ary.length; i++) {
if (ps & Math.pow(2, i)) subset.push(ary[i]);
}
powerSet.push(subset);
}
return powerSet;
}
// Function to calculate the sum of an array.
function getSum(ary) {
return ary.reduce((sum, cur) => {
return sum + cur;
}, 0);
}
function getSubsetBelow(val, ary) {
let bestSoFar;
let bestSoFarSum = 0;
for (let subset of makePowerSet(ary)) {
const sum = getSum(subset);
if (sum > val) continue;
if (sum > bestSoFarSum) {
bestSoFar = subset;
bestSoFarSum = sum;
}
}
console.log("Got a best sum value of", bestSoFarSum, "with the subset", bestSoFar);
}
getSubsetBelow(250, ary)
快速紧凑的解决方案:
function maxSum(input, limit) {
const sums = {};
let max = 0;
const collectSums = (n, i, values) => {
for (; i < input.length; i++) {
const sum = n + input[i];
if (sum <= limit) {
values.push(input[i]);
if (sum >= max && values.length > 1) {
max = sum;
sums[max] = values.slice(); // https://jsperf.com/copying-an-array
}
collectSums(sum, i + 1, values);
}
}
values.pop();
};
collectSums(0, 0, []);
return sums[max] || [];
}
除了输入的必要迭代之外,这个解决方案试图通过不使用昂贵的数组操作来保持低复杂度。只需要复制找到的子集来跟踪可能的组合。尽管如此,可能还有更聪明的解决方案来提高性能。
该方法将返回最后找到的组合,这意味着两个具有不同顺序的相同值的输入列表可能会产生不同的结果:
maxSum([1, 4, 200, 5], 205) == [200, 5]; maxSum([5, 200, 1, 4], 205) == [200, 1, 4];
如果需要所有可能的组合,请替换此行:
sums[max] = values.slice(); // https://jsperf.com/copying-an-array
与此:
sums[max] = sums[max] || [];
sums[max].push(values.slice());
然后返回所有组合:
maxSum([1, 4, 200, 5], 205) == [[1, 4, 200], [200, 5]];
但请注意,这将始终返回数组数组,即使只有一种可能性:
maxSum([40, 138, 29, 450], 250) == [[40, 138, 29]];
基本上,您可以将索引处的元素添加到临时数组中,也可以不添加。然后检查索引是否达到数组的长度,或者总和是否大于所需的总和,然后检查总和并将临时数组添加到结果集中,或者不。
继续,直到访问所有索引。
function getCombinations(array, sum) {
function add(a, b) { return a + b; }
function fork(i, t) {
var r = (result[0] || []).reduce(add, 0),
s = t.reduce(add, 0);
if (i === array.length || s > sum) {
if (s <= sum && t.length && r <= s) {
if (r < s) {
result = [];
}
result.push(t);
}
return;
}
fork(i + 1, t.concat([array[i]]));
fork(i + 1, t);
}
var result = [];
fork(0, []);
return result;
}
console.log(getCombinations([40, 138, 29, 450], 250));
.as-console-wrapper { max-height: 100% !important; top: 0; }
使用递归,编写一个给定整数列表和给定和的程序,将找到总数为给定和的所有数字子集。计算找到的子集数。如果不存在子集,则应指示未找到解决方案。例如,给定列表6、13、3、3,且总和为19,您的程序应找到两个解决方案: 将输入列表中的整数数限制为最多20个整数。仅接受正整数,并使用0标记列表的结尾。以下是运行示例: 这是我的代码,但它只找到一个子集,我想找到所有子集。有什么帮助吗?
给出不同整数的列表 我的想法:< br >一种简单的方法是一个接一个地选择一个元素,看看它形成的完美子集的大小,然后我们可以简单地返回最大值。这将是计算密集型的。< br >有什么好的解决方案吗
我只能想到一个朴素的算法,它列出集合的所有子集,并检查子集的和是否和是否最小,但它是一个指数算法,列出所有子集需要O(2^n)。我能用动态规划在多项式时间内求解吗?
这是我的数据库结构。 城市->地标->景点(每一个都是一个集合) 查询 列出特定城市下的所有景点。
我在Scala中做了一个问题,这是任务语句的摘要: 上述示例的输出: 1 2 3 -1 第一行是数组长度,第二行是整数数组(0 以下是我尝试的:选择的元素并不重要。所以我先对给定整数的列表排序最大。然后我选择了第一个元素,检查它是否大于S,如果不大于S,我也选择了第二个元素,依此类推,直到总和大于或等于S。 我的代码(Scala):
这类似于子集和问题,只是稍有不同,不是检查集合是否有一个和为9的子集,而是我们必须找到这样的子集的个数。我在这里遵循子集和问题的解法。但是我想知道如何修改它来返回子集的计数。