【洛谷贪心算法题】P2240部分背包问题

【解题思路】

1. 贪心策略选择
   • 对于部分背包问题，关键在于如何选择物品放入背包以达到最大价值。由于物品可以分割，遍历排序后的物品数组，根据物品重量和背包剩余容量的关系，决定是将整个物品放入背包还是分割物品放入背包，并更新总价值。。
   • 单位重量价值高的物品，在相同重量下能带来更高的价值。所以，我们优先选择单位重量价值高的物品放入背包。
2. 具体实现步骤
   • 首先，读入物品的数量 、背包容量 以及每个物品的重量 和价值（结构体存储） 。
   • 然后，计算每个物品的单位重量价值，并将物品按照单位重量价值从大到小进行排序（自定义排序）。
   • 接着，遍历排序后的物品列表，依次将物品放入背包。如果当前物品的重量小于等于背包剩余容量，就将整个物品放入背包，更新背包剩余容量和总价值。
   • 如果当前物品的重量大于背包剩余容量，说明不能将整个物品放入背包，此时将物品分割，放入背包剩余容量的部分，计算这部分物品的价值并更新总价值，同时结束循环，因为此时背包已满。

【代码示例】

#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip> 
using namespace std;// 定义物品结构体，包含重量，价值和单位重量价值
struct Item {double weight;double value;double unitValue;
}; // 自定义比较函数，用于按单位重量价值从大到小排序
bool compare(const Item& a, const Item& b) {return a.unitValue > b.unitValue;
} int main() {int n;double m;cin >> n >> m;vector<Item> items(n);for (int i = 0; i < n; i++) {cin >> items[i].weight >> items[i].value;items[i].unitValue = items[i].value / items[i].weight;}// 按单位重量价值排序sort(items.begin(), items.end(), compare);double totalValue = 0;for (int i = 0; i < n; i++) {if (items[i].weight <= m) {m -= items[i].weight;totalValue += items[i].value;} else {// 正确的做法是累加当前物品按比例放入背包后的价值totalValue += items[i].unitValue * m; m=0;}}// 输出结果，保留三位小数cout << fixed << setprecision(2) << totalValue << endl;return 0;
}

注意：

• #include <iomanip> 头文件：使用标准库中与输入输出格式控制相关的功能，具体在代码里用于精确控制输出结果的小数位数。