每日c/c++题 备战蓝桥杯（P2240 【深基12.例1】部分背包问题）

P2240 【深基12.例1】部分背包问题 - 详解与代码实现

一、题目概述

阿里巴巴要在承重为 T 的背包中装走尽可能多价值的金币，共有 N 堆金币，每堆金币有总重量和总价值。金币可分割，且分割后单位价格不变。目标是求出能装走的最大价值。

二、问题分析

这个问题是典型的贪心算法应用场景——部分背包问题。核心在于如何选择金币堆的装入顺序，以实现价值最大化。

关键点：

1. 贪心策略：优先装单位价值（价值 / 重量）高的金币堆，这样在有限的背包容量下，能获得最大价值。
2. 可分割性：金币可分割，意味着可以部分装入某堆金币，这使得问题可以用贪心策略解决，而无需动态规划（如 0-1 背包问题）。

三、解题思路

步骤详解：

1. 计算单位价值：对每堆金币，计算其单位价值（价值 / 重量）。
2. 排序：将金币堆按单位价值从高到低排序，这样可以优先选择价值密度高的金币。
3. 装背包过程：
   • 遍历排序后的金币堆。
   • 若背包剩余容量足够装下整堆金币，则全部装入，并累加对应价值。
   • 若背包剩余容量不足，则装入剩余容量所能容纳的部分金币，价值按比例累加。
   • 直到背包装满或所有金币堆处理完毕。

四、代码实现

#include<bits/stdc++.h>
using namespace std;
struct node
{int num; // 记录金币堆的索引（可省略）double v; // 单位价值
}d[105];
bool cmp(node x, node y)
{if (x.v > y.v) return true;return false;
}
int main()
{int N, T;int m[105] = { 0 }; // 每堆金币的重量int v[105] = { 0 }; // 每堆金币的价值cin >> N >> T;for (int i = 0; i < N; ++i){cin >> m[i] >> v[i];d[i].v = (double) v[i] / (double) m[i]; // 计算单位价值d[i].num = i; // 记录索引（实际未用）}sort(d, d + N, cmp); // 按单位价值从高到低排序double sum = 0;int wei = 0; // 已装重量for (int i = 0; i < N; i++){if(T - wei > 0) // 背包未满{if (wei + m[d[i].num] > T) // 当前堆无法完全装入{sum += (T - wei) * d[i].v; // 装入部分wei = T; // 背包满了}else{sum += d[i].v * m[d[i].num]; // 装入整堆}wei += m[d[i].num]; // 更新已装重量（即使装满 T 后也不影响）}}printf("%.2lf", sum); // 输出保留两位小数return 0;
}

五、代码分析

数据结构：

• 使用结构体 node 存储每堆金币的单位价值和索引（索引也可省略）。
• 数组 m 和 v 分别存储金币堆的重量和价值。

算法流程：

1. 输入读取和预处理：读取金币堆数量 N 和背包承重 T，计算每堆金币的单位价值。
2. 排序：通过自定义比较函数 cmp，将金币堆按单位价值从高到低排序。
3. 贪心装背包：
   • 遍历排序后的金币堆，根据背包剩余容量决定装入整堆还是部分。
   • 累加价值到总价值变量 sum 中。
4. 输出结果：使用 printf 输出总价值，保留两位小数。

六、测试用例与结果验证

输入示例：

4 50
10 60
20 100
30 120
15 45

输出：

240.00

验证过程：

1. 各堆金币的单位价值分别为：
   • 堆 0：60 / 10 = 6.0
   • 堆 1：100 / 20 = 5.0
   • 堆 2：120 / 30 = 4.0
   • 堆 3：45 / 15 = 3.0
2. 排序后顺序为堆 0 → 堆 1 → 堆 2 → 堆 3。
3. 背包容量 T=50：
   • 先装堆 0，重 10，价值 60，剩余容量 40。
   • 装堆 1，重 20，价值 100，剩余容量 20。
   • 装堆 2，重 30，但剩余容量只有 20，装入 20 重量，价值 4 * 20 = 80（单位价值是 4）。
   • 总价值：60 + 100 + 80 = 240.00。

七、总结与拓展

总结：

部分背包问题通过贪心策略（按单位价值排序）可以高效求解。关键在于理解贪心选择的正确性：优先装单位价值高的物品，能保证全局价值最大。

拓展：

1. 0-1 背包问题：物品不可分割，需用动态规划解决。
2. 多约束背包问题：如同时有重量和体积限制，需更复杂的算法。
3. 变种问题：如要求必须装满背包，或物品有依赖关系等。

希望本篇文章能帮助你更好地理解部分背包问题的解法。如果有其他问题或需要进一步探讨，欢迎留言交流！