javascript - 使用 JavaScript 在子集数组之间交换重复值

Question

问题 - 下面的算法循环遍历对象数组并将对象分配给三个子集，使得每个子集的总和非常接近(贪心算法)。如果您运行代码，您会注意到在第一个子集中 p:11 出现了两次，而在第三个子集中 p:10 出现了两次。我不想让 p 值多次出现在同一个数组中。
问题 - 如何在算法中确保 p 的值不会多次出现在同一个子集数组中，因为对象被分配到子集数组，同时确保每个子集数组的总和仍然相同？

let list = [
  {p:2, size:50},{p:4, size:50},{p:5,size:25},
  {p:6, size:167},{p:6, size:167},{p:7, size:50},
  {p:8, size:25},{p:8, size:50},{p:10, size:75},
  {p:10, size:75},{p:11, size:25},{p:11, size:50},
  {p:12, size:25},{p:13, size:50},{p:14,size:25}
]

function balance_load(power_load_array, number_of_phases) {
 const sorted = power_load_array.sort((a, b) => b.size - a.size); // sort descending

 const output = [...Array(number_of_phases)].map((x) => {
   return {
     sum: 0,
     elements: [],
   };
 });

 for (const item of sorted) {
   const chosen_subset = output.sort((a, b) => a.sum - b.sum)[0];
   chosen_subset.elements.push({p:item.p, size:item.size});
   chosen_subset.sum += item.size;
 }

 return output
}

let p = balance_load(list,3)

console.log(p)

Answer 1

答:

How can I ... while making sure the sum of each subset array is still the same?

您不能在每种情况下都保持相同的总和。考虑代码的输出:

sum: 317: [{"p":6,"size":167}, {"p":7,"size":50}, {"p":11,"size":50}, {"p":11,"size":25}, {"p":14,"size":25}, ]
sum: 292: [{"p":6,"size":167}, {"p":4,"size":50}, {"p":13,"size":50}, {"p":8,"size":25}, ]
sum: 300: [{"p":10,"size":75}, {"p":10,"size":75}, {"p":2,"size":50}, {"p":8,"size":50}, {"p":5,"size":25}, {"p":12,"size":25}, ]

在这里，我们可以交换 {p:11 size:25}与 {p:8 size:25}并且总和保持不变。
但是如果是 {p:10 size:75} , 没有其他尺寸为 75 的项目.最接近的情况是将其与 {p:4 size:50} 交换。 .现在总和变为 317,317,275这是不一样的。

最好的解决方案是找到所有组合，没有重复，并选择总和最接近的组合。

错误:
你的算法有错误。考虑一个没有重复的输入:

Power load array:
 [{"p":1,"size":2},{"p":2,"size":10},{"p":3,"size":10},{"p":4,"size":11},{"p":5,"size":11}]

No of phases: 2

您的代码产生以下子集:

sum: 23: [{"p":4,"size":11}, {"p":3,"size":10}, {"p":1,"size":2}, ]
sum: 21: [{"p":5,"size":11}, {"p":2,"size":10}, ]

理想的总和应该是 22,22和分组应该是 11,11和 10,10,2 .

不同的方法:
这是我对贪心算法的看法:

按降序对项目进行排序。

获取 subset limit = total input size/no of subsets

对于每个子集

从输入中挑选项目，这将使我们接近 subset limit .

将剩余项目放在最后一个子集中。或均匀分布。

// DEMO ----------------------------
// 1. no duplicates
let list = [{p: 1, size: 2},
  {p: 2, size: 10}, {p: 3, size: 10},
  {p: 4, size: 11}, {p: 5, size: 11},
]
printInput(list);
printOutput(balance_load(list, 2));


// 2. last two(size:11) are duplicates
list = [{p: 1, size: 2},
  {p: 2, size: 10 }, {p: 3, size: 10},
  {p: 4, size: 11 }, {p: 4, size: 11},
]
printInput(list);
printOutput(balance_load(list, 2));

// 3. original input from the opening post
list = [
  { p: 2, size: 50 }, { p: 4, size: 50 }, { p: 5, size: 25 },
  { p: 6, size: 167 }, { p: 6, size: 167 }, { p: 7, size: 50 },
  { p: 8, size: 25 }, { p: 8, size: 50 }, { p: 10, size: 75 },
  { p: 10, size: 75 }, { p: 11, size: 25 }, { p: 11, size: 50 },
  { p: 12, size: 25 }, { p: 13, size: 50 }, { p: 14, size: 25 }
];
printInput(list);
printOutput(balance_load(list, 3));


// implementation --------------------
function balance_load(power_load_array, number_of_phases) {
  const sortFunction = (a, b) => b.size - a.size;
  const sorted = power_load_array.sort(sortFunction); // sort descending

  const output = [...Array(number_of_phases)].map(_ => ({
    // TODO: can be converted to a proper class
    sum: 0,
    elements: [],

    addItem(item) {
      this.sum += item.size;
      this.elements.push({ ...item });
    },
    addItems(items) {
      items.forEach(e => this.addItem(e));
    },
    contains(item) {
      return this.elements.findIndex(e => e.p === item.p) !== -1;
    },
    toString() {
      let out = `sum: ${this.sum}: <span class='item'>[`;
      this.elements.forEach(e => out += JSON.stringify(e) + ', ');
      out += ']</span>\n';
      return out;
    }
  }));


  let sum = sorted.reduce((a, b) => a + b.size, 0);
  let limit = sum / number_of_phases;
  limit += sorted[sorted.length - 1].size; // average + smallest item

  out.innerHTML += `sum= ${sum}\nsubset limit= ${limit}\n`;

  // fill all subsets one after other
  output.forEach(o => {
    let item = null;

    // first add biggest item
    if (sorted.length > 0) {
      o.addItem(sorted.shift());
    }

    // keep adding to the subset till we reach the average limit
    for (let i = 0; i < sorted.length; i++) {
      item = sorted.shift();
      if ((limit >= o.sum + item.size) && !o.contains(item)) {
        o.addItem(item);
      } else {
        sorted.push(item); // recycle
      }
    }
    sorted.sort(sortFunction);
  });

  // add rest of the stuff to the last subset
  // TODO: add logic to destribute evenly
  output[output.length - 1].addItems(sorted);
  return output
}

function printInput(list) {
  out.innerHTML += `<hr>\nInput: <span class='item'>${JSON.stringify(list)}</span>\n`;
}

function printOutput(list) {
  list.forEach(e => out.innerHTML += e);
}

.item { font-size: .6rem; color: brown; }

<pre id="out"></pre>

请注意，可以通过多种方式改进代码。例如。在排序时，我们可以将重复的项目放在首位，因此避免重复比使总和更接近更优先。
需要用更多的测试用例进行测试。