題目來源：【深基12.例1】部分背包問題 - 洛谷

參考書目：《深入淺出程序設計競賽（基礎篇）》

解題思路：這道題是部分背包，如果金幣不能完整的放入是可以分割的。題目中有若干堆金幣，每堆金幣有一定的重量（m）和價值（v），以及一個最大承重為 t 的背包。目標是通過完全或部分地拿取這些金幣堆，使得背包中的金幣價值最大化。代碼采用貪心算法，通過按價值與重量比降序排序金幣堆，然后迭代地將它們添加到背包中，直到背包裝滿或沒有更多的金幣堆可考慮。

解題步驟：

• 迭代讀取每堆金幣的重量和價值，并存儲在數組 a 中。
• 使用 sort 函數和 cmp 比較函數對金幣堆進行排序。
• 迭代地將每堆金幣加入背包：
  • 如果當前金幣堆的重量大于剩余容量，則跳出循環。
  • 否則，從剩余容量中減去金幣堆的重量，并將其價值加到總價值 ans 上。
• 如果因為一堆金幣無法完全加入而退出循環，將該金幣堆的一部分加入到 ans 中，以填滿剩余容量。
• 最后，打印出總價值 ans，保留兩位小數。

#include<iostream>
#include<algorithm>using namespace std;// 定義結構體來存儲每堆金幣的重量和價值
struct coin {int m, v; // 金幣堆的重量和價值
} a[110];// 比較函數，用于根據價值與重量的比率（性價比）進行排序
bool cmp(coin x, coin y)
{return x.v * y.m > y.v * x.m; // 比較兩堆金幣的性價比
}int main()
{int n, t, c, i;float ans = 0; // 初始化答案變量cin >> n >> t; // 讀入金幣堆數和背包容量c = t; // 背包剩余容量初始化為背包總容量// 讀入每堆金幣的重量和價值for (i = 0; i < n; i++){cin >> a[i].m >> a[i].v;}// 對金幣堆按性價比降序排序sort(a, a + n, cmp);// 遍歷金幣堆，嘗試將它們加入背包for (i = 0; i < n; i++){if (a[i].m > c) break; // 如果當前金幣堆無法完全裝入背包，則跳出循環c -= a[i].m; // 減少背包剩余容量ans += a[i].v; // 增加背包中金幣的總價值}// 如果退出循環是因為一堆金幣無法完全加入，則加入這堆金幣的一部分if (i < n){ans += 1.0 * c / a[i].m * a[i].v; // 加入部分金幣堆，按比例計算價值}// 輸出最終答案，保留兩位小數printf("%.2lf", ans);return 0;
}