鱼C论坛

 找回密码
 立即注册
查看: 1697|回复: 17

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

[复制链接]
发表于 2023-5-7 12:32:38 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
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
本帖最后由 陶远航 于 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,你可以装下一部分金币,其价值为单位价值乘以装下的重量。
改正后的代码如下:
  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. }
复制代码
小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

发表于 2023-5-7 12:34:53 | 显示全部楼层
你点进去发表帖子旁边有个发布悬赏
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2023-5-7 12:35:17 | 显示全部楼层    本楼为最佳答案   
本帖最后由 陶远航 于 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,你可以装下一部分金币,其价值为单位价值乘以装下的重量。
改正后的代码如下:
  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. }
复制代码
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2023-5-7 12:35:44 | 显示全部楼层
不会,
小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

发表于 2023-5-7 12:36:23 | 显示全部楼层
根据题意,这道题需要我们选择一些物品放入背包,使其总质量不超过 $T$ ,并且总价值最大。贪心的思路是将每个物品按单位价值从小到大排序,然后依次选择使得单位价值最低的物品(即价值/重量最小)直到装满或装完为止。

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

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

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


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


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

2. 未初始化变量 `r`

在你的代码中, `r` 表示当前选取的总价值,但没有被初始化为 0 ,所以可能输出错误结果。正确的写法是将其初始化为 0
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2023-5-7 12:36:37 | 显示全部楼层
sfqxx 发表于 2023-5-7 12:34
你点进去发表帖子旁边有个发布悬赏

??在哪你截个图
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2023-5-7 12:41:48 | 显示全部楼层
陈尚涵 发表于 2023-5-7 12:36
??在哪你截个图


                               
登录/注册后可看大图
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

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

这gpt改了还是不行
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

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

gpt写着一半没了
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

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

看着gpt前面一顿讲解好像有道理但代码还过不去
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2023-5-7 12:45:10 | 显示全部楼层

已经发的改不了了?
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 0 反对 1

使用道具 举报

发表于 2023-5-7 12:45:47 | 显示全部楼层
陈尚涵 发表于 2023-5-7 12:45
已经发的改不了了?

是的
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2023-5-7 12:48:44 | 显示全部楼层
屏幕截图 2023-05-07 124201.png
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 0 反对 1

使用道具 举报

发表于 2023-5-7 12:56:26 | 显示全部楼层
  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. }
复制代码
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2023-5-7 12:57:16 | 显示全部楼层
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2023-5-7 12:58:30 | 显示全部楼层

小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2023-5-7 12:59:21 | 显示全部楼层
题解有什么用?抄了会被封号
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2023-5-7 15:48:07 | 显示全部楼层
贪心 , 把 单价最高 的先装
  1. #include <bits/stdc++.h>
  2. using namespace std;

  3. int n, t;
  4. struct coin{
  5.     double price, storage;
  6. } coins[105];
  7. double p, q, ans;

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

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

  14.     cin >> n >> t;
  15.     for(int i = 1; i <= n; i++){
  16.         cin >> p >> q;
  17.         coins[i] = {q/p, p};
  18.     }

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

  20.     for(int i = 1; i <= n; i++){
  21.         if(coins[i].storage <= t){
  22.             ans += coins[i].price * coins[i].storage;
  23.             t -= coins[i].storage;
  24.         }
  25.         else{
  26.             ans += coins[i].price * t;
  27.             break;
  28.         }
  29.     }

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

  31.     return 0;
  32. }
复制代码
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2025-6-11 15:16

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表