找到的功率设定的加权子集和最大值 [英] Finding max value of a weighted subset sum of a power set

问题描述

我有一个稀疏的功率输入设置（即一些组合已经pre-除外）。在发电机组中的每个条目都有了一定的成绩。我想找到，涵盖所有点和最大限度地提高了整体得分相结合。

I've got a sparse power set for an input (ie some combos have been pre-excluded). Each entry in the power set has a certain score. I want to find the combination that covers all points and maximizes the overall score.

例如，假设输入生成如下：

For example, let's say the input is generated as follows:

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 。

Since order doesn't matter, I can convert the combinations into a bitmask & use that as the key. So to read the table: a key of "3" is 011 is base 2, which means linking 0-1 yields a score of 36, whereas 0 individually + 1 individually yields a total sum of 11, therefore the linkage, 0-1, is greater than the sum of its parts 0,1.

在这样做时，我已经减少这一个加权子集和问题，其目的是要找到每一个总结，以15（ 1111 相当于组合基座2）及然后取最大值。这是我坚持。我试着用动态规划，但由于随机性，我不明白我怎么可以做任何削减。例如， 1-2 可能比 1,2 好（在上表中，3有得分高于1+2）。然而 1-3,2 可能优于 1-2,3 或 1 2-3 ）。

In doing so, I've reduced this to a weighted subset sum problem, where the goal is to find every combination that sums to 15 (the equivalent of 1111 in base 2) & then take the max. This is where I'm stuck. I tried using dynamic programming, but due to the randomness, I don't see how I can make any reductions. For example, 1-2 may be better than 1,2 (in the above table, "3" has a higher score than "1" + "2"). However 1-3,2 could be better than 1-2,3 or 1-2-3).

如何可能我有效地找到最佳的组合？ （蛮力是不可行的）。对于本例，该解决方案将是11+4，共为515

How might I efficiently find the optimal mix? (brute force isn't feasible). For this example, the solution would be "11" + "4", for a total of 515.

推荐答案

您要查找的元素之和为15的组合没有任何重叠位，最大限度地提高所选元素的成绩。

You want to find the combination of elements that sum to 15 and don't have any overlapping bits, maximizing the score of the selected elements.

要做到这一点，定义一个函数 bestSubset（使用，有效的），其输入一组它需要使用的元素，而且是有效的子元素被列入但还没有被考虑。它通过考虑一个元素进行操作递归取值的有效集中，考虑两种情况，其中取值时或当它不使用（如果使用则重叠比特可以不再使用的任何元素的话）。

To do this, define a function bestSubset(use, valid) that inputs a set of elements it's required to use and a subset of elements that are valid to be included but have not yet been considered. It operates recursively by considering an element s in the valid set, considering either the case where s is used or when it is not used (if it is used then any elements that overlap bits can no longer be used).

下面是一个JavaScript实现：

Here's a javascript implementation:

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)));

这将返回一组 [4,11] 与得分515，正如你在原来的职位确定。

This returns the set [4, 11] with score 515, as you identified in your original post.

从非稀疏情况下，一些计算实验（又名与 D 数字和目标（2 ^ D）-1 ，包括所有的数字 1，2，...，（2 ^ D）-1 ），我发现这个指数运行中的位数（中的时候，它会检查有效性的递归函数的上面的数字是 O（E ^（1.47d）））。这比蛮力情况下要快得多在其中分别考虑，包括或不包括每一个数字 1，2，...，（2 ^ D）-1 的，它运行在双指数运行 - O（2 ^ 2 ^ D）

From some computational experiments in the non-sparse case (aka with d digits and target (2^d)-1, include all numbers 1, 2, ..., (2^d)-1), I found that this runs exponentially in the number of digits (the number of times it checks validity at the top of the recursive function is O(e^(1.47d))). This is much faster than the brute force case in which you separately consider including or not including each of the numbers 1, 2, ..., (2^d)-1, which runs in doubly exponential runtime -- O(2^2^d).

这篇关于找到的功率设定的加权子集和最大值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！