如何从多商品套餐中找到满足购物清单的最低成本组合？

Hey folks! Let's work through this problem step by step to find the most cost-effective way to meet (and even exceed, if needed) the shopping list requirements.

已知套餐详情 #

目标购物清单需求 #

• 4 Apples
• 1 Orange
• 2 Bananas

通用高效解决思路（编程语言无关） #

步骤1：先算基准成本（作为参考） #

First, calculate the cost if we only buy single-item focused packages for the items that have them:

• 4 Apples would cost 4 * 1$ = 4$ (via Doctors Darling)
• 1 Orange would cost 1.5$ (via Vitamin C)
• Bananas have no standalone package, so we can't cover this need with single-item buys alone.

This gives us a partial cost of 5.5$, but since we still need 2 Bananas, we have to combine with packages that include Bananas.

步骤2：枚举核心套餐组合 #

Focus on packages that cover multiple needs first (like Fruit Overdose, which hits Apples, Oranges, and Bananas at once). For each possible quantity of these core packages (from 0 up to the number needed to max out our largest demand), calculate what remaining items we still need, then find the cheapest way to cover those leftovers.

For our specific case:

• Let's test buying 2x Fruit Overdose: This gives us 4 Apples, 2 Oranges, and 2 Bananas. That fully meets our Apple and Banana needs, and even covers the Orange requirement (with 1 extra Orange). Total cost is 2 * 5$ = 10$.
• If we test 1x Fruit Overdose: It covers 2 Apples, 1 Orange, 1 Banana. We still need 2 Apples and 1 Banana. Covering the Apples costs 2 * 1$ = 2$, but the only way to get that extra Banana is to buy The Exotic (which adds 2 extra Oranges) for 3.5$. Total cost here is 5$ + 2$ + 3.5$ = 10.5$, which is more expensive than the 2x Fruit Overdose option.

步骤3：筛选最优组合 #

Compare all feasible total costs from step 2, and pick the lowest one. For our scenario, the cheapest option is buying 2x Fruit Overdose for 10$—it meets all our needs, even with a small extra Orange, and is the most cost-effective.

额外优化 tips #

• If you already own some items, subtract those from your demand first before running through these steps to cut down on unnecessary purchases.
• For larger shopping lists, calculate the "per-item value" of each package to prioritize the ones that give you the most bang for your buck when covering multiple needs.

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