当前位置: 面试刷题>> 最佳购物计划 (经典算法题500道)


题目描述补充

最佳购物计划

在一个大型在线商城中,有多种商品可供购买,每种商品有不同的价格和折扣率。顾客可以购买任意数量的商品,但商城规定,若顾客购买的商品总金额达到一定额度,可以享受额外的满减优惠(如满300减50)。请编写一个算法,帮助顾客计算购买一系列商品时的最佳购物计划,即顾客需要购买哪些商品(数量不限),以使得在满足满减条件的前提下,实际支付的总金额最少。

输入

  1. 商品列表,包含每个商品的ID、单价、以及可选的折扣率(无折扣的商品折扣率为0)。
  2. 满减优惠条件,如“满300减50”。
  3. 顾客希望购买的商品ID列表及初始购买数量(顾客可以调整购买数量)。

输出

  1. 调整后的商品购买数量列表,使得总支付金额最少。
  2. 顾客需要支付的总金额。

示例代码

以下分别提供PHP、Python、JavaScript的示例代码实现。由于这是一个复杂的问题,涉及到组合优化和动态规划等高级算法,这里给出一个简化的贪心算法版本,仅供学习参考。

PHP 示例

function optimalShoppingPlan($items, $discountRule, $desiredItems) {
    $totalCost = 0;
    $adjustedQuantities = [];
    $threshold = intval(explode('满', $discountRule)[1]); // 提取满减门槛
    $discount = intval(explode('减', $discountRule)[1]); // 提取减免金额

    foreach ($desiredItems as $itemId => $quantity) {
        if (!isset($items[$itemId])) continue;
        $item = $items[$itemId];
        $price = $item['price'] * (1 - $item['discount'] / 100); // 计算折扣后价格
        $totalCost += $price * $quantity;
        $adjustedQuantities[$itemId] = $quantity;

        // 贪心调整购买数量以达到满减条件
        while ($totalCost >= ($threshold + $discount) && $quantity < 10) { // 假设最多购买10个
            $totalCost += $price;
            $quantity++;
            $adjustedQuantities[$itemId] = $quantity;
        }
    }

    // 应用满减
    if ($totalCost >= $threshold) {
        $totalCost -= $discount;
    }

    return [$adjustedQuantities, $totalCost];
}

// 示例数据
$items = [
    1 => ['price' => 100, 'discount' => 0],
    2 => ['price' => 200, 'discount' => 10],
    3 => ['price' => 50, 'discount' => 0]
];
$discountRule = "满300减50";
$desiredItems = [1 => 2, 2 => 1];

list($adjustedQuantities, $totalCost) = optimalShoppingPlan($items, $discountRule, $desiredItems);
echo "调整后购买数量: " . json_encode($adjustedQuantities) . "\n";
echo "需要支付的总金额: " . $totalCost . "\n";

Python 示例

def optimal_shopping_plan(items, discount_rule, desired_items):
    threshold, discount = map(int, discount_rule.split('满')[1].split('减'))
    total_cost = 0
    adjusted_quantities = {}

    for item_id, quantity in desired_items.items():
        if item_id not in items:
            continue
        item = items[item_id]
        price = item['price'] * (1 - item['discount'] / 100)
        total_cost += price * quantity
        adjusted_quantities[item_id] = quantity

        # 贪心调整
        while total_cost >= (threshold + discount) and quantity < 10:
            total_cost += price
            quantity += 1
            adjusted_quantities[item_id] = quantity

    # 应用满减
    if total_cost >= threshold:
        total_cost -= discount

    return adjusted_quantities, total_cost

# 示例数据
items = {
    1: {'price': 100, 'discount': 0},
    2: {'price': 200, 'discount': 10},
    3: {'price': 50, 'discount': 0}
}
discount_rule = "满300减50"
desired_items = {1: 2, 2: 1}

adjusted_quantities, total_cost = optimal_shopping_plan(items, discount_rule, desired_items)
print("调整后购买数量:", adjusted_quantities)
print("需要支付的总金额:", total_cost)

JavaScript 示例

function optimalShoppingPlan(items, discountRule, desiredItems) {
    const [thresholdStr, discountStr] = discountRule.split('满')[1].split('减');
    const threshold = parseInt(thresholdStr, 10);
    const discount = parseInt(discountStr, 10);
    let totalCost = 0;
    const adjustedQuantities = {};

    for (const [itemId, quantity] of Object.entries(desiredItems)) {
        if (!items[itemId]) continue;
        const { price, discount: itemDiscount } = items[itemId];
        const adjustedPrice = price * (1 - itemDiscount / 100);
        totalCost += adjustedPrice * quantity;
        adjustedQuantities[itemId] = quantity;

        // 贪心调整
        while (totalCost >= (threshold + discount) && quantity < 10) {
            totalCost += adjustedPrice;
            quantity++;
            adjustedQuantities[itemId] = quantity;
        }
    }

    // 应用满减
    if (totalCost >= threshold) {
        totalCost -= discount;
    }

    return [adjustedQuantities, totalCost];
}

// 示例数据
const items = {
    1: { price: 100, discount: 0 },
    2: { price: 200, discount: 10 },
    3: { price: 50, discount: 0 }
};
const discountRule = "满300减50";
const desiredItems = { 1: 2, 2: 1 };

const [adjustedQuantities, totalCost] = optimalShoppingPlan(items, discountRule, desiredItems);
console.log("调整后购买数量:", adjustedQuantities);
console.log("需要支付的总金额:", totalCost);

注意:以上代码为简化示例,实际应用中可能需要考虑更多因素,如不同商品组合的价格策略、库存限制等。此外,对于复杂的优化问题,可能需要采用更高级的算法如动态规划、整数规划或启发式搜索算法等。码小课网站中有更多相关内容分享给大家学习。

推荐面试题