使用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)

- tim_woods

---

所有的 p 值都是正整数吗？ - Redu

是的，p 值将始终为正整数。子集数组的数量始终为 1、2 或 3。用户最多只能选择相同的 p 值三次。 - tim_woods

Answer 1

答案：

如何在确保每个子集数组的总和仍相同的情况下进行操作？

无法在每种情况下保持总和相同。请考虑您代码的输出：

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:8 size:25}交换{p:11 size:25}，总和仍然相同。
但是，在{p:10 size:75}的情况下，没有其他大小为75的项目。最接近的情况是将其与{p:4 size:50}交换。现在总和变为317,317,275，它们不相同。

---

Bug:
您的算法存在漏洞。考虑一个没有重复项的输入：

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。

---

不同的方法:
这是我个人的贪心算法：

1. 按降序排列项目。
2. 获取子集极限=输入总大小/子集数
3. 对于每个子集
4. • 从输入中选择可以使我们接近子集极限的项目。
5. 将剩余项放入最后一子集。或均匀分配。

// 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>

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

- the Hutt

Answer 2

这个问题可以作为一个整数线性优化问题来解决，其中有一个连续变量t，以及每个元素i和组合j的一个变量xij：

- x_ij：如果将list的第i个元素分配给组j，则等于1，否则等于0。

我们有以下系数：

- ci：list中第i个元素（list[i][:size]）的成本 - pi：list中第i个元素（list[i][:p]）的价值 - S：由两个或多个list元素共享的唯一值list[i][:p]构成的集合。 - U(s)：对于每个s∈S，U(s)是list中满足list[i][:p]==s的元素i的集合。

公式如下：

- (1) min t - subject to: - (2) t >= ∑_i x_ijc_ij for each j - (3) ∑_j x_ij = 1 for each i - (4) ∑_U(s) x_ij <= 1 for each j and s in S - (5) x_ij equals 0 or 1 for all i,j pairs

(1)和(2)寻求最小化最大组成本的minimax解决方案，这倾向于减少总成本并使成本在组之间平衡。

(3)要求将list的每个元素分配到恰好一个组中。

(4)确保没有两个具有相同list[:p]值的list元素被分配到同一组中。

- Cary Swoveland