本帖最后由 陶远航 于 2023-5-7 12:36 编辑
这题是一个部分背包问题,需要用贪心算法来求解。你的题意理解没有问题,但是你的代码有一些错误。我可以帮你指出并改正:
你的第18行的while循环是多余的,因为你只需要判断一次背包容量是否大于当前金币重量即可,不需要反复判断。
你的第19行的if条件应该是t >= mv[ i].m,而不是t > mv[ i].m,因为如果t等于mv[ i].m,也可以装下当前金币。
你的第21行的r += mv[ i].v应该改为r += mv[ i].v * mv[ i].m,因为你需要计算当前金币的总价值,而不是单位价值。
你的第22行的else语句应该加上r += mv[ i].v * t / mv[ i].m,因为如果t小于mv[ i].m,你可以装下一部分金币,其价值为单位价值乘以装下的重量。
改正后的代码如下:
- #include <iostream>
- #include <algorithm>
- #include <iomanip>
- using namespace std;
- struct coin{
- double m, v;
- }mv[105];
- bool cmp(coin a, coin b){
- return a.m / a.v < b.m / b.v;
- }
- int main(){
- int n;
- double t;
- cin >> n >> t;
- for (int i = 1; i <= n; i++) cin >> mv[i].m >> mv[i].v;
- sort(mv+1, mv+1+n, cmp);
- double r;
- for (int i = 1; i <= n; i++) {
- if (t >= mv[i].m){ // 如果背包容量大于等于当前金币重量
- t -= mv[i].m; // 背包容量减去当前金币重量
- r += mv[i].v * mv[i].m; // 答案加上当前金币总价值
- } else { // 如果背包容量小于当前金币重量
- r += mv[i].v * t / mv[i].m; // 答案加上装下的部分金币价值
- break; // 结束循环
- }
- }
- cout << fixed << setprecision(2) << r; // 输出答案,保留两位小数
- return 0;
- }
复制代码