求组合的最大收益？

Question

我有如下数据结构

from数组是我可以使用的材料列表，其中name是每个材料的名字，num是材料的数量
target数组中是可以使用材料制作的组合配方，其中composition是配方的组合，每个材料最多一次，value是该配方的收益
现在需要使用提供的材料制作出不同的组合，材料不需要全部用掉，组合可以重复使用，也不用全部结合
请问怎么编写程序求出最大收益呢？

Answer 1

这个问题应该可以使用贪婪算法（可能我想的不够全面）；

将 target 进行排序，排序标准是平均价格排序，也就是使用 value / composition.length ,求出每个材料平均收益最大的放在前面，如果最大收益相同，再按照 composition.length小的排在前面，换而言之，就是将使用最少材料的最大收益先优先制作出来。

代码如下：

const compose = (from, target) => {
  const fromObj = from.reduce((t, v) => {
    if (v.num > 0) t[v.name] = v.num;
    return t;
  }, {});
  target = target.filter((r) => r.composition.some((rc) => fromObj[rc]) && r.value > 0);
  target.sort((a, b) => {
    const avgA = a.value / a.composition.length,
      avgB = b.value / b.composition.length;
    if (avgA > avgB) return -1;
    else if (avgA < avgB) return 1;
    return a.composition.length <= b.composition.length ? -1 : 1;
  });
  const res = [];
  for (let i = 0; i < target.length; i++) {
    const t = target[i];
    let can = false;
    while (t.composition.every((r) => fromObj[r] > 0)) {
      if (!t.num) t.num = 0;
      t.num++;
      t.composition.forEach((r) => fromObj[r]--);
      if (!can) can = true;
    }
    if (can) res.push(t);
  }
  return res;
};