我为输入设置了稀疏功率集（即已经预先排除了一些组合）。电源组中的每个条目都有一定的分数。我想找到涵盖所有要点并最大化总分的组合。
例如，假设输入生成如下：
function powerset(ary) {
var ps = [[]];
for (var i = 0; i < ary.length; i++) {
for (var j = 0, len = ps.length; j < len; j++) {
ps.push(ps[j].concat(ary[i]));
}
}
return ps;
}
function generateScores() {
var sets = powerset([0, 1, 2, 3]);
sets.pop() //remove the last entry to make it "sparse"
var scores = {};
for (var i = 1; i < sets.length; i++) { //skip 0-len
var set = sets[i];
var val = 0;
for (var j = 0; j < set.length; j++) {
val |= (1 << set[j]);
}
scores[val] = ~~Math.pow(((Math.random()+1)*4),set.length);
}
return scores;
}
var scores = generateScores();
输出看起来像这样：
{
"1": 7,
"2": 4,
"3": 36,
"4": 5,
"5": 32,
"6": 50,
"7": 84,
"8": 4,
"9": 30,
"10": 50,
"11": 510,
"12": 47,
"13": 73,
"14": 344,
}
由于顺序无关紧要，我可以将组合转换为位掩码并将其用作键。所以要阅读表格：“3”的关键是011是基数2，这意味着链接0-1得到36分，而0个人+ 1个单独产生总和11，因此联系，0-1，是大于其各部分0,1的总和。
在这样做的过程中，我将其减少为加权子集和问题，其目标是找到总和为15的每个组合（相当于基数2中的1111）然后取最大值。这就是我被困住的地方。我尝试使用动态编程，但由于随机性，我不知道如何进行任何减少。例如，1-2可能比1,2更好（在上表中，“3”的得分高于“1”+“2”）。然而，1-3,2可能比1-2,3或1-2-3更好。
我怎样才能有效地找到最佳组合？ （蛮力不可行）。对于该示例，解决方案将是“11”+“4”，总共515。
您希望找到总和为15且没有任何重叠位的元素组合，从而最大化所选元素的分数。
为此，定义一个函数bestSubset(use, valid)，它输入一组需要使用的元素，以及一些有效的元素子集，但尚未被考虑。它通过考虑有效集合中的元素s来递归地操作，考虑使用s的情况或不使用var scores = {1:7, 2:4, 3:36, 4:5, 5:32, 6:50, 7:84, 8:4, 9:30, 10:50, 11:510, 12:47, 13:73, 14:344};
var S = [];
for (var prop in scores) {
S.push([parseInt(prop), scores[prop]]);
}
var n = 15; // Target sum
var k = S.length; // Number of weights
function bestSubset(use, valid) {
if (valid.length == 0) {
var weightSum = 0;
var scoreSum = 0;
var weights = [];
for (var ct=0; ct < use.length; ct++) {
weightSum += S[use[ct]][0];
weights.push(S[use[ct]][0]);
scoreSum += S[use[ct]][1];
}
if (weightSum == n) {
return [weights, scoreSum];
} else {
return false;
}
}
// Don't use valid[0]
var valid1 = [];
for (ct=1; ct < valid.length; ct++) {
valid1.push(valid[ct]);
}
var opt1 = bestSubset(use, valid1);
// Use valid[0]
var use2 = JSON.parse(JSON.stringify(use));
use2.push(valid[0]);
var valid2 = [];
for (ct=1; ct < valid.length; ct++) {
if ((S[valid[0]][0] & S[valid[ct]][0]) == 0) {
valid2.push(valid[ct]);
}
}
var opt2 = bestSubset(use2, valid2);
if (opt1 === false) {
return opt2;
} else if (opt2 === false || opt1[1] >= opt2[1]) {
return opt1;
} else {
return opt2;
}
}
var initValid = [];
for (var ct=0; ct < S.length; ct++) {
initValid.push(ct);
}
alert(JSON.stringify(bestSubset([], initValid)));
的情况（如果使用它，那么任何重叠位的元素都不能再使用）。
这是一个javascript实现：
[4, 11]这将返回您在原始帖子中标识的设置d，得分为515。
从非稀疏情况下的一些计算实验（又名(2^d)-1数字和目标1, 2, ..., (2^d)-1，包括所有数字O(e^(1.47d))），我发现它在指数上以指数形式运行（它在递归顶部检查有效性的次数）功能是1, 2, ..., (2^d)-1）。这比你分别考虑包括或不包括每个数字O(2^2^d)的蛮力情况要快得多，var scores = {1: 7, 2: 4, 3: 36, 4: 5, 5: 32, 6: 50, 7: 84, 8: 4, 9: 30, 10: 50, 11: 510, 12: 47, 13: 73, 14: 344};
var S = [];
var keys = Object.keys(scores);
for (i = 0; i < keys.length; i++) {
S.push([parseInt(keys[i]), scores[keys[i]]]);
}
var n = Math.pow(2,range.length) -1; // Target sum
var k = S.length; // Number of weights
// best[i, j] is scored in position i*(k+1) + j
var best = [];
// Base case
for (var j = 0; j <= k; j++) {
best.push([[], 0]);
}
// Main loop
for (var i = 1; i <= n; i++) {
best.push(false); // j=0 case infeasible
for (j = 1; j <= k; j++) {
var opt1 = best[i * (k + 1) + j - 1];
var opt2 = false;
if (S[j - 1][0] <= i) {
var parent = best[(i - S[j - 1][0]) * (k + 1) + j - 1];
if (parent !== false) {
opt2 = [parent[0].slice(), parent[1]];
var child = S[j - 1];
var opt2BitSig = 0;
for (var m = 0; m < opt2[0].length; m++) {
opt2BitSig |= opt2[0][m];
}
if ((opt2BitSig & child[0])) {
opt2 = false;
} else {
opt2[0].push(child[0]);
opt2[1] += child[1];
}
}
}
if (opt1 === false) {
best.push(opt2);
} else if (opt2 === false || opt1[1] >= opt2[1]) {
best.push(opt1);
} else {
best.push(opt2);
}
}
}
console.log(JSON.stringify(best[n * (k + 1) + k]));
以双指数运行时运行 - qazxswpoi。
对于谷歌搜索，我使用@josilber提供的答案，没有递归和重叠保护（见下文）。由于JS中的递归深度限制为1000，我不得不使用循环。不幸的是，对于我的用例，我仍然没有内存，所以看起来我必须使用一些启发式。
qazxswpoi
一种不同的方法（一如既往）：
您可以为总和小于单个重量的每个值获得权重。因此wa + wb <wc和a + b = c，这导致简单的权重系统。
为了更好地理解权重，它必须是自然数，也就是整数。
为什么不简单地使用数字本身进行少量缩减以使总和小于单个权重。
我取数字并取值作为重量。另外，我将它们的值减少1，所以：
哦= 1，b = 2，c = 3 W + wb <wc W = 0，wb = 1，wc = 2 => 0 + 1 <2
公式：weightn = n - 1
对于每个加数，你得到-1的malus。因此，对于更多的加数，您得到的数字小于原始数字的权重。
重量15（14）应大于重量4（3）和重量11（10）之和。
数字：14> 3 + 10
我的意思是，这里不需要程序代码。