1 条题解

  • 0
    @ 2025-10-19 22:44:25

    题目解析 这道题有从 -m 到 m 共 2m+1 种重量的物品,每种有多个。要选出一些物品,让总重量正好等于 L,并且选的物品数量尽量多。 核心思路

    1. 问题转换 先算出如果所有物品都选的总重量 S 和总数量 T: • 如果 S = L,答案就是 T • 如果 S > L,需要移除一些物品来减少重量 • 如果 S < L,需要移除一些物品来增加重量(通过移除负重量物品)
    2. 贪心预处理 代码先进行贪心调整: • 当当前总重量比 L 大时,移除正重量物品(从最重的开始) • 当当前总重量比 L 小时,移除负重量物品(从最轻的开始) 这样调整后,剩下的重量差很小,可以用DP解决。
    3. 动态规划处理 把问题看成多重背包:每种重量 i 的物品有 a_i 个,要凑出目标重量。 使用单调队列优化: • 对每种重量,按余数分组处理 • 用队列维护最优决策 • 时间复杂度从 O(n×W×C) 优化到 O(n×W)

    算法复杂度 • 贪心部分:O(m) • DP部分:O(m³) - 对于 m ≤ 300 可以接受 • 空间:O(m²) 样例说明 样例1:m=2, L=5, 物品数量=[2,3,1,1,4] • 初始全选总重量为2,需要增加到5 • 经过调整找到选9个物品的方案 样例2:无法调整到目标重量,输出不可能 样例3:只有重量1的物品,选5个正好重量为5 这种方法先用贪心处理大范围调整,再用DP保证小范围最优性,是该问题的有效解法。

    • 1

    信息

    ID
    3540
    时间
    1000ms
    内存
    256MiB
    难度
    10
    标签
    递交数
    1
    已通过
    1
    上传者