当前位置： 面试刷题>> 最佳购物计划 (经典算法题500道)
### 题目描述补充
**最佳购物计划**
在一个大型在线商城中，有多种商品可供购买，每种商品有不同的价格和折扣率。顾客可以购买任意数量的商品，但商城规定，若顾客购买的商品总金额达到一定额度，可以享受额外的满减优惠（如满300减50）。请编写一个算法，帮助顾客计算购买一系列商品时的最佳购物计划，即顾客需要购买哪些商品（数量不限），以使得在满足满减条件的前提下，实际支付的总金额最少。
**输入**：
1. 商品列表，包含每个商品的ID、单价、以及可选的折扣率（无折扣的商品折扣率为0）。
2. 满减优惠条件，如“满300减50”。
3. 顾客希望购买的商品ID列表及初始购买数量（顾客可以调整购买数量）。
**输出**：
1. 调整后的商品购买数量列表，使得总支付金额最少。
2. 顾客需要支付的总金额。
### 示例代码
以下分别提供PHP、Python、JavaScript的示例代码实现。由于这是一个复杂的问题，涉及到组合优化和动态规划等高级算法，这里给出一个简化的贪心算法版本，仅供学习参考。
#### PHP 示例
```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 示例
```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 示例
```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);
```
**注意**：以上代码为简化示例，实际应用中可能需要考虑更多因素，如不同商品组合的价格策略、库存限制等。此外，对于复杂的优化问题，可能需要采用更高级的算法如动态规划、整数规划或启发式搜索算法等。码小课网站中有更多相关内容分享给大家学习。