小明购物问题(C语言数据结构）

小明购物问题

一、问题核心 商场规则为“买1件商品送1件等值或低价商品”，小明购N件商品，需通过合理搭配“付费商品+赠送商品”，实现总付费金额最小。

二、贪心策略 核心逻辑：优先为价格高的商品付费，将价格低的商品作为赠品，最大化利用赠送规则减少付费。 -合理性：若A商品价格＞B商品价格，仅能选择付费A、赠送B（总付费A）；若反向操作，因B价格低于A，不符合“赠品格价≤付费商品价格”规则，无法实现，故高价付费、低价赠送是唯一最优局部选择，最终能推导全局最优。

三、解题步骤 1. 数据结构定义：用结构体存储商品编号（No）和价格（v），方便区分和排序。 2. 排序处理：将所有商品按价格降序排列（从贵到便宜），这是贪心策略的关键，确保优先处理高价商品。 3. 组合配对：排序后每2件为一组，第1件（高价）作为付费商品，第2件（低价）作为赠送商品，每组仅需支付高价商品费用。 4. 特殊情况处理：若商品数N为奇数，最后剩余的1件商品无对应赠品，需单独付费。

四、关键逻辑说明 - 排序：通过选择排序实现价格降序，确保高价商品优先被处理，为后续最优配对奠定基础。 - 配对：以步长2遍历排序后的商品数组，每组第1个元素计入总付费，第2个元素作为赠品，高效利用规则。 - 总付费计算：累加所有付费商品价格，即为最小总付费额。 ## 五、核心结论 该问题通过“价格降序排序+两两分组（高价付费、低价赠送）”的贪心策略，能快速得到最小付费额，充分体现贪心算法“局部最优→全局最优”的核心思想，且满足“贪心选择性质”和“最优子结构”，是贪心算法的典型应用。