javascript - 计算杠铃获得特定重量所需的重量

Question

我正在尝试计算一组最佳的板来放在杠铃上以达到所需的重量。它运行良好，但问题是它总是会找到第一个可能的重量低于目标重量。

例如，如果您希望您的杠铃重 29kg，您可以将 27.5kg 或 30kg 给定下面的一组盘子，其中每个板 block 都被假定为一对。知道这两个选项后，您会选择 30kg，因为它更接近 29 而不是 27.5。

在这个例子中，我只是让它计算 27.5，但我还没有想出如何在 if 语句失败后返回并计算最接近的可能权重。

const BAR = 20;

const PLATES = [
  1.25,
  2.5,
  2.5,
  5,
  5,
  10,
  10,
  20,
  20,
];

const sumPlates = (plates) => {
  return plates.reduce((acc, plate) => {
    return acc + (plate * 2);
  }, 0);
};

const rack = (targetWeight) => {
  const sortedPlates = PLATES.sort((a, b) => b - a);

  const rackedPlates = sortedPlates.reduce((acc, plate) => {
    if ((BAR + (plate * 2) + sumPlates(acc)) > targetWeight) {
      // Calculate here the closest possible rack weight
      return acc;
    }

    acc.push(plate);

    return acc;
  }, []);

  return {
    targetWeight,
    barbellWeight: BAR + sumPlates(rackedPlates),
    plates: rackedPlates,
  };
};

console.log(rack(47)); // gives 45 but should give 47.5
console.log(rack(29)); // gives 27.5 but should give 30

Answer 1

它实际上是一个Change-making problem的修改版本，它本身就是背包问题的修改版本。

根据给定权重的大小和类型，你可以在链接中使用动态规划解决方案找到所有可能的组合，并进行O(N)迭代找到最接近的一个目标重量。

---

但是鉴于您当前的实现，我只会执行以下操作:

var x = rack(targetSum);
var y = rack(2*targetSum - x);
ans = the closer one to targetSum