C++ 贪心算法求解最大价值金币问题 - 详细代码与解析

{"title":"C++ 贪心算法实现最大价值金币问题","description":"阿里巴巴走进了装满宝藏的藏宝洞。藏宝洞里面有 N(N \le 100)N(N≤100) 堆金币，第 ii 堆金币的总重量和总价值分别是 m_i,v_i(1\le m_i,v_i \le 100)m \ \ i\\ ,v \ \ i\\ (1≤m \ \ i\\ ,v \ \ i\\ ≤100)。阿里巴巴有一个承重量为 T(T \le 1000)T(T≤1000) 的背包，但并不一定有办法将全部的金币都装进去。他想装走尽可能多价值的金币。所有金币都可以随意分割，分割完的金币重量价值比（也就是单位价格）不变。请问阿里巴巴最多可以拿走多少价值的金币？","keywords":"贪心算法, C++, 金币, 最大价值, 背包问题","content":"贪心算法的思路是按照单位价格从高到低进行排序，然后依次选择单位价格最高的金币放入背包，直到背包达到承重量为止。\\n\\n具体实现如下：\\n\\ncpp\\\n#include <iostream>\\\n#include <algorithm>\\\nusing namespace std;\\\n\\\nstruct Treasure {\\\n int weight;\\\n int value;\\\n double unitPrice;\\\n};\\\n\\\nbool compare(Treasure t1, Treasure t2) {\\\n return t1.unitPrice > t2.unitPrice;\\\n}\\\n\\\ndouble getMaxValue(Treasure treasures[], int n, int T) {\\\n for (int i = 0; i < n; i++) {\\\n treasures[i].unitPrice = (double)treasures[i].value / treasures[i].weight;\\\n }\\\n sort(treasures, treasures + n, compare);\\\n \\\n double maxValue = 0.0;\\\n int currentWeight = 0;\\\n for (int i = 0; i < n; i++) {\\\n if (currentWeight + treasures[i].weight <= T) {\\\n maxValue += treasures[i].value;\\\n currentWeight += treasures[i].weight;\\\n } else {\\\n double remainWeight = T - currentWeight;\\\n maxValue += treasures[i].unitPrice * remainWeight;\\\n break;\\\n }\\\n }\\\n \\\n return maxValue;\\\n}\\\n\\\nint main() {\\\n int N, T;\\\n cin >> N >> T;\\\n Treasure treasures[N];\\\n for (int i = 0; i < N; i++) {\\\n cin >> treasures[i].weight >> treasures[i].value;\\\n }\\\n \\\n double maxValue = getMaxValue(treasures, N, T);\\\n cout << maxValue << endl;\\\n \\\n return 0;\\\n}\\\n\\n\\n输入样例：\\n\\\n3 50\\\n10 60\\\n20 100\\\n30 120\\\n\\n\\n输出样例：\\n\\\n240\\\n\\n\\n解释：阿里巴巴可以选择第三堆金币的全部（单位价格最高），然后再选择第二堆金币的一半（单位价格次高），总共可以拿走 120 + 100/2 = 240 的价值的金币。