分数背包
进阶分数背包因物品可分，贪心策略天然有效。
// 算法讲解
分数背包
输入偶数个整数：重量、价值交替。背包容量 50。
待机
速度 中
待机 ⌨1double fractionalKnapsack(int W, vector<int>& wt, vector<int>& val) {
2 int n = wt.size();
3 vector<int> idx(n);
4 iota(idx.begin(), idx.end(), 0);
5 sort(idx.begin(), idx.end(), [&](int a, int b) {
6 return (double)val[a] / wt[a] > (double)val[b] / wt[b];
7 });
8 double total = 0;
9 int remain = W;
10 for (int i : idx) {
11 int take = min(wt[i], remain);
12 total += (double)val[i] * take / wt[i];
13 remain -= take;
14 if (remain == 0) break;
15 }
16 return total;
17}
复杂度分析
时间 O(n log n)
空间 O(n)
最优 O(n) 已排序时
最坏 O(n log n)
算法讲解
分数背包问题允许把物品切成任意比例装入背包，因此"先装性价比最高的"就是最优策略。
按单位价值（价值/重量）从大到小排序后，依次尽量装满，直到背包容积用完。
和 0-1 背包的区别在于：0-1 背包不能分割物品，所以贪心不保证最优；而分数背包可分，贪心恰好正确。
这正好帮助理解"贪心正确性依赖于问题是否具有贪心选择性质"。