求最优产品组合算法：用最少产品填充目标尺寸且剩余最小

你的问题本质上是一个无界背包问题的变体（产品可以重复选择），当前的贪心算法之所以无法得到你想要的结果，是因为贪心只追求局部最优（每次拿最多的大尺寸产品），但无法考虑全局的最优组合——尤其是当产品尺寸之间没有倍数关系时，贪心很容易错过更优的解。

为什么你的贪心算法不适用？ #

你的代码每次尽可能多地取当前最大尺寸的产品，对于目标72，得到的是2个25、1个15、2个3（总尺寸71，剩余1，共5个产品）。如果你的期望是2个25、1个15、3个3（总尺寸74，剩余2，共6个产品），那说明你的最优标准可能和常规的“剩余最小+数量最少”不一致——要么是你允许总尺寸超过目标，要么是你有额外的限制（比如必须使用所有类型的产品）。但不管怎样，贪心算法都无法灵活处理这类需要全局判断的场景。

正确的解法：动态规划 #

动态规划可以帮我们跟踪每个可能尺寸对应的最少产品数量，从而找到全局最优解。下面是针对两种常见需求的实现：

需求1：总尺寸不超过目标，剩余最小且产品数量最少

var products = [{"name":"product 1", "size":25},{"name":"product 2", "size":15},{"name":"product 3", "size":3}];
var target = 72;

// dp[s] = 达到尺寸s所需的最少产品数，初始化为无穷大表示不可达
const dp = new Array(target + 1).fill(Infinity);
dp[0] = 0; // 尺寸0需要0个产品
// 记录每个尺寸的前驱产品，用于回溯组合
const prev = new Array(target + 1).fill(null);

// 遍历每个产品
for (const product of products) {
    // 遍历所有可能的尺寸
    for (let s = product.size; s <= target; s++) {
        // 如果用当前产品能得到更少的数量，更新状态
        if (dp[s - product.size] + 1 < dp[s]) {
            dp[s] = dp[s - product.size] + 1;
            prev[s] = { product, prevSize: s - product.size };
        }
    }
}

// 找到最优尺寸：最大的可达尺寸（剩余最小）
let bestSize = 0;
for (let s = target; s >= 0; s--) {
    if (dp[s] < Infinity) {
        bestSize = s;
        break;
    }
}

// 回溯得到产品组合
const combination = {};
let current = prev[bestSize];
while (current) {
    const name = current.product.name;
    combination[name] = (combination[name] || 0) + 1;
    current = prev[current.prevSize];
}

// 输出结果
console.log(`目标尺寸${target}的最优组合：`);
Object.entries(combination).forEach(([name, count]) => {
    console.log(`${count} x ${name}`);
});
console.log(`总尺寸：${bestSize}，剩余：${target - bestSize}，产品总数：${dp[bestSize]}`);

运行结果：

目标尺寸72的最优组合：
2 x product 1
1 x product 2
2 x product 3
总尺寸：71，剩余：1，产品总数：5

需求2：总尺寸≥目标，超过量最小且产品数量最少

如果你的需求是必须覆盖目标尺寸（允许超过），只需调整dp数组的范围和最优解的查找逻辑：

var products = [{"name":"product 1", "size":25},{"name":"product 2", "size":15},{"name":"product 3", "size":3}];
var target = 72;
const maxProductSize = Math.max(...products.map(p => p.size));
const maxSize = target + maxProductSize; // 考虑超过目标的最大可能尺寸

const dp = new Array(maxSize + 1).fill(Infinity);
dp[0] = 0;
const prev = new Array(maxSize + 1).fill(null);

for (const product of products) {
    for (let s = product.size; s <= maxSize; s++) {
        if (dp[s - product.size] + 1 < dp[s]) {
            dp[s] = dp[s - product.size] + 1;
            prev[s] = { product, prevSize: s - product.size };
        }
    }
}

// 找到最优尺寸：≥target，差值最小且产品数量最少
let bestSize = target;
let minDiff = Infinity;
let minCount = Infinity;

for (let s = target; s <= maxSize; s++) {
    if (dp[s] === Infinity) continue;
    const diff = s - target;
    if (diff < minDiff || (diff === minDiff && dp[s] < minCount)) {
        minDiff = diff;
        minCount = dp[s];
        bestSize = s;
    }
}

// 回溯组合
const combination = {};
let current = prev[bestSize];
while (current) {
    const name = current.product.name;
    combination[name] = (combination[name] || 0) + 1;
    current = prev[current.prevSize];
}

// 输出结果
console.log(`目标尺寸${target}的最优组合：`);
Object.entries(combination).forEach(([name, count]) => {
    console.log(`${count} x ${name}`);
});
console.log(`总尺寸：${bestSize}，超过目标：${minDiff}，产品总数：${minCount}`);

运行结果：

目标尺寸72的最优组合：
3 x product 1
总尺寸：75，超过目标：3，产品总数：3

这个结果比你期望的组合更优（产品数量更少），如果你的期望有额外限制（比如必须使用多种产品），可以在动态规划的状态中加入更多约束条件。

总结 #

• 贪心算法只适合产品尺寸成倍数关系的场景，无法处理全局最优的背包问题。
• 动态规划是这类问题的标准解法，通过跟踪每个尺寸的最少产品数，能找到符合各种最优标准的组合。

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