问题描述 #

给定以下背包问题变种的约束条件：

• 小偷可选择n个物品进行盗窃，背包容量为M
• 每个物品i对应重量w_i、价值p_i
• 核心特殊条件：物品按重量递增排序的顺序，与按价值递减排序的顺序完全一致（即若w₁ ≤ w₂ ≤ ... ≤ wₙ，则必有p₁ ≥ p₂ ≥ ... ≥ pₙ，反之亦然）

贪心算法设计 #

你提出的贪心算法（GA）逻辑可明确为：

1. 预处理排序：按重量递增（等价于价值递减）的顺序对物品排序（若输入已满足该顺序可跳过此步）
2. 贪心选择：依次选取当前剩余物品中价值最高（即重量最轻）的物品放入背包，直到加入下一个物品会导致总重量超过背包容量M时停止

正确性证明（完善版） #

我们采用反证法+交换论证的思路来严谨证明算法的最优性：

假设前提 #

假设存在某个输入实例，使得贪心算法GA得到的解G不是最优解。设最优解为OS，且OS的总价值严格大于G的总价值，即Σp(OS) > Σp(G)。

统一物品排序 #

• 将G中的物品按价值递减（即重量递增）排序，记为G = {g₁, g₂, ..., gₖ}，其中g₁是价值最高（重量最轻）的物品，总重量W_G = Σw(gᵢ) ≤ M
• 将OS中的物品按价值递减排序，记为OS = {o₁, o₂, ..., oₘ}，总重量W_OS = Σw(oᵢ) ≤ M

推导矛盾：交换论证 #

1. 找到第一个差异物品：
   寻找第一个索引t，使得g_t ≠ o_t（若所有前k个物品都相同，但OS包含更多物品，则GA在选取时必然可以继续加入剩余物品，与GA的停止条件矛盾，因此该t必然存在）。此时g₁=o₁, ..., g_{t-1}=o_{t-1}，且g_t ≠ o_t。

2. 基于特殊条件的交换合理性：
   根据GA的选择规则，g_t是选取前t-1个物品后，剩余物品中价值最高（重量最轻）的物品。结合题目特殊条件，价值越高则重量越轻，因此w(g_t) ≤ w(o_t)，且p(g_t) ≥ p(o_t)。
   进一步可推导单位重量价值的性质：对于任意i < j，因w_i ≤ w_j且p_i ≥ p_j，可得p_i/w_i ≥ p_j/w_j（反证：若p_i/w_i < p_j/w_j，则p_i*w_j < p_j*w_i，但w_j ≥ w_i、p_i ≥ p_j，左边乘积必然≥右边，矛盾）。这说明GA的选择本质是每次选取单位重量价值最高的物品，符合经典贪心的核心逻辑。

3. 交换后仍为最优解：
   将OS中的o_t替换为g_t，得到新解OS'。此时：

   • 总重量：W_OS' = W_OS - w(o_t) + w(g_t) ≤ W_OS ≤ M，满足背包容量约束
   • 总价值：Σp(OS') = Σp(OS) - p(o_t) + p(g_t) ≥ Σp(OS)，即OS'的总价值不低于原最优解OS，因此OS'也是最优解。

4. 迭代交换逼近贪心解：
   重复上述交换过程，将OS中所有与G不同的物品逐步替换为G中的物品，最终得到的解OS''的总价值≥OS，且物品集合与G完全一致（或为G的子集，但子集的总价值不可能超过G，与OS是最优解矛盾）。这直接推翻了“OS严格优于G”的假设。

综上，贪心算法GA得到的解必然是最优解。

时间复杂度分析 #

• 排序阶段：若输入物品未按要求排序，需执行一次基于重量或价值的排序，时间复杂度为O(n log n)
• 贪心选取阶段：遍历物品并累加重量，直到超过容量，时间复杂度为O(n)
• 总时间复杂度：由排序步骤主导，为O(n log n)

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