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

陈尚涵

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

1. #include <iostream>
   
2. #include <algorithm>
   
3. #include <iomanip>
   
4. using namespace std;
   
5. struct coin{
   
6.         double m, v;
   
7. }mv[105];
   
8. bool cmp(coin a, coin b){
   
9.         return a.m / a.v < b.m / b.v;
   
10. }
    
11. int main(){
    
12.         int n;
    
13.         double t;
    
14.         cin >> n >> t;
    
15.         for (int i = 1; i <= n; i++) cin >> mv[i].m >> mv[i].v;
    
16.         sort(mv+1, mv+1+n, cmp);
    
17.         double r;
    
18.         for (int i = 1; i <= n; i++) while (true) if (t > mv[i].m){
    
19.                 t -= mv[i].m;
    
20.                 r += mv[i].v;
    
21.         } else break;
    
22.         cout << fixed << setprecision(2) << r;
    
23.         return 0;
    
24. }

复制代码

还有，悬赏贴怎么发？

最佳答案

月排行榜 / 总排行榜

陶远航

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，你可以装下一部分金币，其价值为单位价值乘以装下的重量。
改正后的代码如下：

1. #include <iostream>
   
2. #include <algorithm>
   
3. #include <iomanip>
   
4. using namespace std;
   
5. struct coin{
   
6. double m, v;
   
7. }mv[105];
   
8. bool cmp(coin a, coin b){
   
9. return a.m / a.v < b.m / b.v;
   
10. }
    
11. int main(){
    
12. int n;
    
13. double t;
    
14. cin >> n >> t;
    
15. for (int i = 1; i <= n; i++) cin >> mv[i].m >> mv[i].v;
    
16. sort(mv+1, mv+1+n, cmp);
    
17. double r;
    
18. for (int i = 1; i <= n; i++) {
    
19.    if (t >= mv[i].m){ // 如果背包容量大于等于当前金币重量
    
20.      t -= mv[i].m; // 背包容量减去当前金币重量
    
21.      r += mv[i].v * mv[i].m; // 答案加上当前金币总价值
    
22.    } else { // 如果背包容量小于当前金币重量
    
23.      r += mv[i].v * t / mv[i].m; // 答案加上装下的部分金币价值
    
24.      break; // 结束循环
    
25.    }
    
26. }
    
27. cout << fixed << setprecision(2) << r; // 输出答案，保留两位小数
    
28. return 0;
    
29. }

复制代码

跳转到最佳答案楼层

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，你可以装下一部分金币，其价值为单位价值乘以装下的重量。
改正后的代码如下：

1. #include <iostream>
   
2. #include <algorithm>
   
3. #include <iomanip>
   
4. using namespace std;
   
5. struct coin{
   
6. double m, v;
   
7. }mv[105];
   
8. bool cmp(coin a, coin b){
   
9. return a.m / a.v < b.m / b.v;
   
10. }
    
11. int main(){
    
12. int n;
    
13. double t;
    
14. cin >> n >> t;
    
15. for (int i = 1; i <= n; i++) cin >> mv[i].m >> mv[i].v;
    
16. sort(mv+1, mv+1+n, cmp);
    
17. double r;
    
18. for (int i = 1; i <= n; i++) {
    
19.    if (t >= mv[i].m){ // 如果背包容量大于等于当前金币重量
    
20.      t -= mv[i].m; // 背包容量减去当前金币重量
    
21.      r += mv[i].v * mv[i].m; // 答案加上当前金币总价值
    
22.    } else { // 如果背包容量小于当前金币重量
    
23.      r += mv[i].v * t / mv[i].m; // 答案加上装下的部分金币价值
    
24.      break; // 结束循环
    
25.    }
    
26. }
    
27. cout << fixed << setprecision(2) << r; // 输出答案，保留两位小数
    
28. return 0;
    
29. }

复制代码

liuhongrun2022

不会，

sfqxx

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

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

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

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

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

复制代码

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

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

陶远航

1. #include<bits/stdc++.h>
   
2. using namespace std;
   
3. struct Node
   
4. {
   
5.         int m,v;
   
6. }a[105];
   
7. bool cmp(const Node &a,const Node &b)
   
8. {
   
9.         //按单位价格降序排序，交叉相乘避免精度损失
   
10.         //a.v/a.m > b.v/b.m  ---->a.v*b.m > b.v*a.m
    
11.         return a.v*b.m > b.v*a.m;       
    
12. }
    
13. int main()
    
14. {
    
15.         int n,t;
    
16.         scanf("%d%d",&n,&t);
    
17.         for(int i=0;i<n;i++)
    
18.                 scanf("%d%d",&a[i].m,&a[i].v);
    
19.         sort(a,a+n,cmp);//按单位价格降序排序
    
20.         double sum=0;
    
21.         for(int i=0;i<n;i++)
    
22.         {
    
23.                 if(t>=a[i].m)//背包能放下整堆金币
    
24.                 {
    
25.                         t-=a[i].m;//背包容量减少
    
26.                         sum+=a[i].v;
    
27.                 }
    
28.                 else//不能放下整堆金币
    
29.                 {
    
30.                         sum+=1.0*a[i].v/a[i].m*t;//将背包装满
    
31.                         break;
    
32.                 }
    
33.         }
    
34.         printf("%.2f\n",sum);
    
35.         return 0;
    
36. }
    

复制代码

陈尚涵

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

这个是题解？

陶远航

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

嗯

sfqxx

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

柿子饼同学

贪心 , 把 单价最高 的先装

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. int n, t;
   
5. struct coin{
   
6.     double price, storage;
   
7. } coins[105];
   
8. double p, q, ans;
   
9. 
   
10. inline bool cmp(coin a, coin b){
    
11.     return a.price > b.price;
    
12. }
    
13. 
    
14. int main(){
    
15.     ios::sync_with_stdio(0);
    
16.     cin.tie(0);
    
17. 
    
18.     cin >> n >> t;
    
19.     for(int i = 1; i <= n; i++){
    
20.         cin >> p >> q;
    
21.         coins[i] = {q/p, p};
    
22.     }
    
23. 
    
24.     sort(coins + 1, coins + n + 1, cmp);
    
25. 
    
26.     for(int i = 1; i <= n; i++){
    
27.         if(coins[i].storage <= t){
    
28.             ans += coins[i].price * coins[i].storage;
    
29.             t -= coins[i].storage;
    
30.         }
    
31.         else{
    
32.             ans += coins[i].price * t;
    
33.             break;
    
34.         }
    
35.     }
    
36. 
    
37.     cout << fixed << setprecision(2) << ans << endl;
    
38. 
    
39.     return 0;
    
40. }

复制代码