Google Sheets环境下5元素约束背包问题求解方案咨询

核心思路 #

这是带数量约束的0-1背包问题（固定选5个元素，总重量≤100，总价值最大），直接遍历所有C(100,5)=75287520种组合完全不现实，得用分治+筛选的高效策略。

具体实现步骤 #

1. 预处理筛选 #

• 剔除单个weight>100的元素（选这类元素直接超总重量，无意义）
• 按value/weight比值降序排序，优先保留性价比高的元素，比如先取前60个（范围足够覆盖最优解即可，后续若结果不理想再扩大）

2. 分治拆分计算 #

把筛选后的元素平分成两组A和B：

• 对每组生成所有1-3个元素的组合，记录每个组合的元素个数、总weight、总value、元素列表
• 对每组的组合按元素个数分组，再按总weight升序排序，同时维护「最大value前缀数组」：比如k个元素的组合排序后，每个位置存储到当前为止的最大value，后续查找时能快速定位不超重量限制的最优组合

3. 组合匹配最优解 #

遍历所有元素个数拆分方式（A组1个+B组4个、A组2个+B组3个、A组3个+B组2个、A组4个+B组1个）：

• 对A组的k个元素组合，计算剩余可承受重量=100-该组合总weight，剩余需选元素数=5-k
• 在B组对应元素数的组合列表中，用二分查找找到总weight≤剩余重量的最大value组合
• 计算两组组合的总value，记录所有可能中的最大值及对应元素列表

4. Google Apps Script代码实现 #

直接在Google Sheets中编写脚本执行：

function findOptimal5Elements() {
  const sheet = SpreadsheetApp.getActiveSpreadsheet().getActiveSheet();
  const data = sheet.getDataRange().getValues();
  const header = data.shift();
  const elementCol = header.indexOf('Element');
  const weightCol = header.indexOf('weight');
  const valueCol = header.indexOf('value');

  // 预处理：剔除超重元素，按性价比降序排序
  const filtered = data.filter(row => row[weightCol] <= 100)
    .map(row => ({
      name: row[elementCol],
      weight: Number(row[weightCol]),
      value: Number(row[valueCol]),
      ratio: Number(row[valueCol])/Number(row[weightCol])
    }))
    .sort((a,b) => b.ratio - a.ratio);
  
  // 取前60个候选元素
  const candidates = filtered.slice(0,60);
  const mid = Math.floor(candidates.length/2);
  const groupA = candidates.slice(0,mid);
  const groupB = candidates.slice(mid);

  // 生成组内1-3个元素的所有组合，并分组预处理
  function generateCombinations(arr) {
    const combinations = [];
    // 1个元素
    for(let i=0;i<arr.length;i++) {
      combinations.push({count:1, weight:arr[i].weight, value:arr[i].value, elements:[arr[i].name]});
    }
    // 2个元素
    for(let i=0;i<arr.length;i++) {
      for(let j=i+1;j<arr.length;j++) {
        combinations.push({count:2, weight:arr[i].weight+arr[j].weight, value:arr[i].value+arr[j].value, elements:[arr[i].name, arr[j].name]});
      }
    }
    // 3个元素
    for(let i=0;i<arr.length;i++) {
      for(let j=i+1;j<arr.length;j++) {
        for(let k=j+1;k<arr.length;k++) {
          combinations.push({count:3, weight:arr[i].weight+arr[j].weight+arr[k].weight, value:arr[i].value+arr[j].value+arr[k].value, elements:[arr[i].name, arr[j].name, arr[k].name]});
        }
      }
    }
    // 按元素个数分组，排序并维护最大value前缀
    const grouped = {};
    combinations.forEach(comb => {
      if(!grouped[comb.count]) grouped[comb.count] = [];
      grouped[comb.count].push(comb);
    });
    for(const count in grouped) {
      grouped[count].sort((a,b) => a.weight - b.weight);
      let maxVal = 0;
      grouped[count] = grouped[count].map(comb => {
        maxVal = Math.max(maxVal, comb.value);
        return {...comb, maxValueUpTo: maxVal};
      });
    }
    return grouped;
  }

  const combA = generateCombinations(groupA);
  const combB = generateCombinations(groupB);

  let maxTotalValue = 0;
  let bestElements = [];

  // 遍历所有元素个数拆分组合
  const splits = [[1,4],[2,3],[3,2],[4,1]];
  splits.forEach(([countA, countB]) => {
    if(!combA[countA] || !combB[countB]) return;
    combA[countA].forEach(a => {
      if(a.weight >= 100) return;
      const remainingWeight = 100 - a.weight;
      // 二分查找B组最优组合
      let left = 0, right = combB[countB].length - 1;
      let bestBIdx = -1;
      while(left <= right) {
        const mid = Math.floor((left+right)/2);
        if(combB[countB][mid].weight <= remainingWeight) {
          bestBIdx = mid;
          left = mid + 1;
        } else {
          right = mid -1;
        }
      }
      if(bestBIdx !== -1) {
        const totalValue = a.value + combB[countB][bestBIdx].maxValueUpTo;
        if(totalValue > maxTotalValue) {
          maxTotalValue = totalValue;
          // 找到对应最大value的B组组合
          const bComb = combB[countB].find(comb => comb.weight <= remainingWeight && comb.value === combB[countB][bestBIdx].maxValueUpTo);
          bestElements = [...a.elements, ...bComb.elements];
        }
      }
    });
  });

  // 输出结果到新工作表
  const resultSheet = SpreadsheetApp.getActiveSpreadsheet().getSheetByName('Result') || SpreadsheetApp.getActiveSpreadsheet().insertSheet('Result');
  resultSheet.clear();
  resultSheet.getRange(1,1).setValue('最优元素组合');
  resultSheet.getRange(2,1,bestElements.length,1).setValues(bestElements.map(name => [name]));
  resultSheet.getRange(1,2).setValue('总重量');
  resultSheet.getRange(2,2).setValue(bestElements.reduce((sum, name) => {
    const item = candidates.find(i => i.name === name);
    return sum + item.weight;
  }, 0));
  resultSheet.getRange(1,3).setValue('总价值');
  resultSheet.getRange(2,3).setValue(maxTotalValue);
}

5. 手动简化方案（无需脚本） #

• 按value降序排序，选前5个检查总weight是否≤100，满足则作为候选
• 按value/weight降序排序，选前5个检查重量
• 从高value元素开始，尝试替换其中一个为低weight高性价比的元素，逐步调整直到找到符合要求的最大value组合

注意事项 #

• 预处理的筛选数量可调整，若第一次结果不理想，可扩大到前80个元素，计算量仍远小于全遍历
• 脚本若超时，可进一步减少候选元素数量，或优化组合生成逻辑

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