我有一个输入的稀疏幂集(即一些组合已被预先排除)。幂集中的每个条目都有一定的分数。我想找到涵盖所有点并使总分最大化的组合。
例如,假设输入生成如下:
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,
}
由于顺序无关紧要,我可以将组合转换为位掩码并将其用作 key 。所以阅读表格:“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
或未使用它的情况(如果使用它,则任何元素不能再使用重叠位)。
这是一个 javascript 实现:
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)));
这将返回得分为 515 的集合 [4, 11]
,如您在原始帖子中所确定的那样。
来自非稀疏情况下的一些计算实验(又名 d
数字和目标 (2^d)-1
,包括所有数字 1, 2, ..., (2^d)-1
), 我发现这在位数上呈指数运行(它在递归函数顶部检查有效性的次数是 O (e^(1.47d))
)。这比您分别考虑包括或不包括每个数字 1, 2, ..., (2^d)-1
的蛮力情况要快得多,后者以双指数运行运行时 -- O(2^2^d)
。
关于javascript - 查找幂集的加权子集和的最大值,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/32486329/