[已解决]T_T这题怎么wa了，我哪错了？怎么做啊？

陈尚涵

https://www.luogu.com.cn/problem/P2240这题
恶补一下贪心出问题了，是我题意理解有问题吗？还是代码哪里错了？这题怎么做？

#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++) while (true) if (t > mv[i].m){
                t -= mv[i].m;
                r += mv[i].v;
        } else break;
        cout << fixed << setprecision(2) << r;
        return 0;
}

还有，悬赏贴怎么发？

最佳答案

月排行榜 / 总排行榜

陶远航

2023-5-7 12:35:17

这题是一个部分背包问题，需要用贪心算法来求解。你的题意理解没有问题，但是你的代码有一些错误。我可以帮你指出并改正：

你的第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;
}

跳转到最佳答案楼层

sfqxx

你点进去发表帖子旁边有个发布悬赏

陶远航

这题是一个部分背包问题，需要用贪心算法来求解。你的题意理解没有问题，但是你的代码有一些错误。我可以帮你指出并改正：

你的第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;
}

liuhongrun2022

不会，

sfqxx

根据题意，这道题需要我们选择一些物品放入背包，使其总质量不超过 $T$ ，并且总价值最大。贪心的思路是将每个物品按单位价值从小到大排序，然后依次选择使得单位价值最低的物品（即价值/重量最小）直到装满或装完为止。

在你给出的代码中，排序策略和常见的贪心策略一致。但是选择物品的过程有几点问题：

1. 循环条件应当判断当前物品是否可以继续选取

如果某个物品已经不能选取了，那么就要跳出循环，否则将陷入死循环。因此，你需要加入一个“判断物品是否已全部选取”的条件：

for (int i = 1; i <= n; i++) {
    // 判断下一个物品是否可以选取
    if (mv[i].m > t) continue;
    while (true) {
        // 选择该物品并扣除相应重量，更新总价值
        t -= mv[i].m;
        r += mv[i].v;
        // 如果背包无法再次容纳下该物品，则退出循环
        if (t < mv[1].m) break;
    }
}

注意，在这里我将内层循环抽离出来，防止无用的比较导致时间超限。此外，我也增加了一个优化：如果剩余的重量已经小于最轻的物品，则提前退出循环，这样可以减少无用的比较次数。

2. 未初始化变量 `r`

在你的代码中， `r` 表示当前选取的总价值，但没有被初始化为 0 ，所以可能输出错误结果。正确的写法是将其初始化为 0

陈尚涵

sfqxx 发表于 2023-5-7 12:34
你点进去发表帖子旁边有个发布悬赏

？？在哪你截个图

liuhongrun2022

陈尚涵 发表于 2023-5-7 12:36
？？在哪你截个图

                               
登录/注册后可看大图

陈尚涵

陶远航 发表于 2023-5-7 12:35
这题是一个部分背包问题，需要用贪心算法来求解。你的题意理解没有问题，但是你的代码有一些错误。我可以帮 ...

这gpt改了还是不行

陈尚涵

sfqxx 发表于 2023-5-7 12:36
根据题意，这道题需要我们选择一些物品放入背包，使其总质量不超过 $T$ ，并且总价值最大。贪心的思路是将 ...

gpt写着一半没了

陈尚涵

陶远航 发表于 2023-5-7 12:35
这题是一个部分背包问题，需要用贪心算法来求解。你的题意理解没有问题，但是你的代码有一些错误。我可以帮 ...

看着gpt前面一顿讲解好像有道理但代码还过不去

陈尚涵

liuhongrun2022 发表于 2023-5-7 12:41

已经发的改不了了？

liuhongrun2022

陈尚涵 发表于 2023-5-7 12:45
已经发的改不了了？

是的

sfqxx

陶远航

#include<bits/stdc++.h>
using namespace std;
struct Node
{
        int m,v;
}a[105];
bool cmp(const Node &a,const Node &b)
{
        //按单位价格降序排序，交叉相乘避免精度损失
        //a.v/a.m > b.v/b.m  ---->a.v*b.m > b.v*a.m
        return a.v*b.m > b.v*a.m;        
}
int main()
{
        int n,t;
        scanf("%d%d",&n,&t);
        for(int i=0;i<n;i++)
                scanf("%d%d",&a[i].m,&a[i].v);
        sort(a,a+n,cmp);//按单位价格降序排序
        double sum=0;
        for(int i=0;i<n;i++)
        {
                if(t>=a[i].m)//背包能放下整堆金币
                {
                        t-=a[i].m;//背包容量减少
                        sum+=a[i].v;
                }
                else//不能放下整堆金币
                {
                        sum+=1.0*a[i].v/a[i].m*t;//将背包装满
                        break;
                }
        }
        printf("%.2f\n",sum);
        return 0;
}

陈尚涵

陶远航 发表于 2023-5-7 12:56

这个是题解？

陶远航

陈尚涵 发表于 2023-5-7 12:57
这个是题解？

嗯

sfqxx

题解有什么用？抄了会被封号

柿子饼同学

贪心 , 把 单价最高 的先装

#include <bits/stdc++.h>
using namespace std;

int n, t;
struct coin{
    double price, storage;
} coins[105];
double p, q, ans;

inline bool cmp(coin a, coin b){
    return a.price > b.price;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> t;
    for(int i = 1; i <= n; i++){
        cin >> p >> q;
        coins[i] = {q/p, p};
    }

    sort(coins + 1, coins + n + 1, cmp);

    for(int i = 1; i <= n; i++){
        if(coins[i].storage <= t){
            ans += coins[i].price * coins[i].storage;
            t -= coins[i].storage;
        }
        else{
            ans += coins[i].price * t;
            break;
        }
    }

    cout << fixed << setprecision(2) << ans << endl;

    return 0;
}