如何正确实现低总价高数量的最优商品选择函数？

我自行编写了findOptimalProducts函数，旨在给定预算内筛选出总价最低且总数量最高的最优商品，但函数输出结果不符合预期。以下是我的代码及正确结果示例，请求修正该函数以实现需求：

原函数代码 #

function findOptimalProducts(products, budget) {
    const getPrice = (priceString) => parseFloat(priceString.replace(/,/g, ""));
    const getQuantity = (quantityString) => parseFloat(quantityString.slice(1).replace(/K/g, "")) * (quantityString.endsWith("K") ? 1000 : 1);

    // 按单位价格升序排序
    products.sort((a, b) => {
        const quantityA = getQuantity(a.quantity);
        const quantityB = getQuantity(b.quantity);
        const priceA = getPrice(a.price);
        const priceB = getPrice(b.price);
        return (priceA / quantityA) - (priceB / quantityB);
    });

    let selectedProducts = [];
    let totalQuantity = 0;
    let totalPrice = 0;

    // 遍历排序后的商品
    for (const product of products) {
        const pricePerUnit = getPrice(product.price) / getQuantity(product.quantity);
        const quantity = getQuantity(product.quantity);
        const productCost = pricePerUnit * quantity;

        // 判断加入当前商品是否超预算
        if (totalPrice + productCost <= budget) {
            selectedProducts.push(product);
            totalQuantity += quantity;
            totalPrice += productCost;
        } else {
            // 容错逻辑：超预算在100以内则继续遍历
            if (totalPrice + productCost > budget + 100) {
                continue;
            }
        }
    }

    return {
        selectedProducts,
        totalQuantity,
        totalPrice,
    };
}

const products = [
    { "title": "Apple", "quantity": "+2.14K", "price": "800,000" },
    { "title": "Orange", "quantity": "+1.44K", "price": "200,000" },
    { "title": "Banana", "quantity": "+900", "price": "70,000" },
    { "title": "Grape", "quantity": "+96", "price": "90,000" },
    { "title": "Strawberry", "quantity": "+800", "price": "130,000" },
];

// 原测试用例注释
// findOptimalProducts(products, 1000000); // Banana, Orange, Strawberry and Grape
// findOptimalProducts(products, 800000); // Banana, Orange, Strawberry and Grape
// findOptimalProducts(products, 300000); // Banana and Orange
// findOptimalProducts(products, 20000); // Nothing

预期正确结果示例 #

预算: $1M
结果: "Apple", "Banana" 和 "Strawberry"

预算: $800K
结果: "Orange", "Banana", "Grape" 和 "Strawberry"

预算: $300K
结果: "Orange" 和 "Banana"

预算: $200K
结果: "Banana" 和 "Strawberry"

问题分析 #

原函数采用贪心算法（按单位价格升序排序后依次选取），但这种策略无法保证得到总价最低且总数量最高的最优组合：

• 贪心算法只考虑当前局部最优，忽略了全局组合的可能性，比如放弃低单位价格的商品，组合其他商品可能获得更高数量或更低总价。
• 代码中的预算容错逻辑（budget + 100）无实际意义，反而会导致不符合预算的商品被错误考虑。

修正后的函数代码 #

function findOptimalProducts(products, budget) {
    // 预处理：统一转换商品价格和数量为数值类型
    const processedProducts = products.map(product => {
        const price = parseFloat(product.price.replace(/,/g, ""));
        const quantityStr = product.quantity.slice(1);
        const quantity = parseFloat(quantityStr.replace(/K/g, "")) * (quantityStr.endsWith("K") ? 1000 : 1);
        return { ...product, price, quantity };
    });

    // 初始化DP数组：dp[budget] 存储对应预算下的最优状态
    // 状态结构：{ maxQuantity: 最大数量, minPrice: 对应总价, selected: 选中商品列表 }
    const dp = Array(budget + 1).fill(null).map(() => ({
        maxQuantity: 0,
        minPrice: 0,
        selected: []
    }));

    // 遍历每个商品，更新DP状态
    for (const product of processedProducts) {
        // 逆序遍历预算，避免重复选取同一商品（0-1背包标准处理）
        for (let currentBudget = budget; currentBudget >= product.price; currentBudget--) {
            const remainingBudget = currentBudget - product.price;
            const newQuantity = dp[remainingBudget].maxQuantity + product.quantity;
            const newPrice = dp[remainingBudget].minPrice + product.price;

            // 判断是否需要更新状态：数量更大，或数量相同但总价更低
            if (newQuantity > dp[currentBudget].maxQuantity || 
                (newQuantity === dp[currentBudget].maxQuantity && newPrice < dp[currentBudget].minPrice)) {
                dp[currentBudget] = {
                    maxQuantity: newQuantity,
                    minPrice: newPrice,
                    selected: [...dp[remainingBudget].selected, product]
                };
            }
        }
    }

    // 查找预算内的全局最优解（可能存在预算未花完但组合更优的情况）
    let bestState = dp[budget];
    for (let i = budget; i >= 0; i--) {
        if (dp[i].maxQuantity > bestState.maxQuantity || 
            (dp[i].maxQuantity === bestState.maxQuantity && dp[i].minPrice < bestState.minPrice)) {
            bestState = dp[i];
        }
    }

    // 转换回原数据格式（价格带千分位）
    return {
        selectedProducts: bestState.selected.map(p => ({
            title: p.title,
            quantity: p.quantity,
            price: p.price.toLocaleString()
        })),
        totalQuantity: bestState.maxQuantity,
        totalPrice: bestState.minPrice
    };
}

// 测试用例
const products = [
    { "title": "Apple", "quantity": "+2.14K", "price": "800,000" },
    { "title": "Orange", "quantity": "+1.44K", "price": "200,000" },
    { "title": "Banana", "quantity": "+900", "price": "70,000" },
    { "title": "Grape", "quantity": "+96", "price": "90,000" },
    { "title": "Strawberry", "quantity": "+800", "price": "130,000" },
];

// 验证预期结果
console.log(findOptimalProducts(products, 1000000)); // Apple, Banana, Strawberry
console.log(findOptimalProducts(products, 800000)); // Orange, Banana, Grape, Strawberry
console.log(findOptimalProducts(products, 300000)); // Orange, Banana
console.log(findOptimalProducts(products, 200000)); // Banana, Strawberry

修正逻辑说明 #

1. 预处理数据：提前将所有商品的价格和数量转换为数值，避免重复解析字符串，提升效率。
2. 动态规划（0-1背包变种）：
   • 用DP数组记录每个预算额度下的最优状态，解决贪心算法无法覆盖全局最优的问题。
   • 逆序遍历预算，确保每个商品只能被选中一次。
3. 状态更新规则：当加入当前商品后，若新组合的数量更大，或数量相同但总价更低，则更新当前预算的最优状态。
4. 全局最优查找：遍历所有不超过预算的状态，确保找到真正符合要求的最优组合（可能存在预算未耗尽但组合更优的情况）。

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