JavaScript中如何根据指定字段值增删数组元素使Cost总和接近目标值

问题解答 #

JavaScript 没有内置可以直接实现该需求的 API，这个需求本质是经典的0-1背包问题：目标是从details数组中选出元素子集，满足子集Cost总和不超过charge值，且总和尽可能大。
下面是可直接运行的最优实现：

function adjustDetails(data) {
  return data.map(item => {
    const { details, charge } = item;
    // 先计算所有Cost总和，总和不超过charge直接返回原数据
    const totalCost = details.reduce((sum, d) => sum + d.Cost, 0);
    if (totalCost <= charge) return {...item};

    const itemCount = details.length;
    // dp[i][w]表示前i个元素，总上限w时能拿到的最大Cost总和
    const dp = Array.from({length: itemCount + 1}, () => Array(charge + 1).fill(0));
    // 记录元素选中状态，用于回溯拿到选中的元素
    const selected = Array.from({length: itemCount + 1}, () => Array(charge + 1).fill(false));

    // 动态规划计算最大总和
    for (let i = 1; i <= itemCount; i++) {
      const currentCost = details[i-1].Cost;
      for (let weight = 0; weight <= charge; weight++) {
        if (currentCost <= weight && dp[i-1][weight - currentCost] + currentCost > dp[i-1][weight]) {
          dp[i][weight] = dp[i-1][weight - currentCost] + currentCost;
          selected[i][weight] = true;
        } else {
          dp[i][weight] = dp[i-1][weight];
        }
      }
    }

    // 回溯找到所有选中的元素
    let remainingLimit = charge;
    const newDetails = [];
    for (let i = itemCount; i > 0; i--) {
      if (selected[i][remainingLimit]) {
        newDetails.unshift(details[i-1]);
        remainingLimit -= details[i-1].Cost;
      }
    }

    return {
      ...item,
      details: newDetails
    };
  });
}

// 测试你的示例数据
const data = [
  {
    "details": [
      {"Name": "DataSet1", "Severity": "4", "Cost": 20},
      {"Name": "DataSet2", "Severity": "4", "Cost": 30},
      {"Name": "DataSet3", "Severity": "4", "Cost": 25}
    ],
    "charge": 45
  }
];
console.log(adjustDetails(data));

补充说明 #

1. 上述实现的时间复杂度为O(n*charge)，n为details数组元素个数，对于绝大多数业务场景性能足够。如果charge数值特别大，可以优化为滚动数组实现降低空间复杂度。
2. 如果details的元素数量很少（比如小于20个），也可以直接枚举所有子集计算总和找最优解，代码更简洁。
3. 你给出的示例输出中charge值为50属于笔误，原输入charge为45，执行上述代码后输出的charge会保留原数值，details总和为45，完全匹配你的需求。

内容的提问来源于stack exchange，提问作者user2951325