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;
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.m >> mv.v;
sort(mv+1, mv+1+n, cmp);
double r;
for (int i = 1; i <= n; i++) while (true) if (t > mv.m){
t -= mv.m;
r += mv.v;
} else break;
cout << fixed << setprecision(2) << r;
return 0;
}
还有，悬赏贴怎么发？
你点进去发表帖子旁边有个发布悬赏 本帖最后由 陶远航 于 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;
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.m >> mv.v;
sort(mv+1, mv+1+n, cmp);
double r;
for (int i = 1; i <= n; i++) {
if (t >= mv.m){ // 如果背包容量大于等于当前金币重量
t -= mv.m; // 背包容量减去当前金币重量
r += mv.v * mv.m; // 答案加上当前金币总价值
} else { // 如果背包容量小于当前金币重量
r += mv.v * t / mv.m; // 答案加上装下的部分金币价值
break; // 结束循环
}
}
cout << fixed << setprecision(2) << r; // 输出答案，保留两位小数
return 0;
} 不会， 根据题意，这道题需要我们选择一些物品放入背包，使其总质量不超过 $T$ ，并且总价值最大。贪心的思路是将每个物品按单位价值从小到大排序，然后依次选择使得单位价值最低的物品（即价值/重量最小）直到装满或装完为止。
在你给出的代码中，排序策略和常见的贪心策略一致。但是选择物品的过程有几点问题：
1. 循环条件应当判断当前物品是否可以继续选取
如果某个物品已经不能选取了，那么就要跳出循环，否则将陷入死循环。因此，你需要加入一个“判断物品是否已全部选取”的条件：
for (int i = 1; i <= n; i++) {
// 判断下一个物品是否可以选取
if (mv.m > t) continue;
while (true) {
// 选择该物品并扣除相应重量，更新总价值
t -= mv.m;
r += mv.v;
// 如果背包无法再次容纳下该物品，则退出循环
if (t < mv.m) break;
}
}
注意，在这里我将内层循环抽离出来，防止无用的比较导致时间超限。此外，我也增加了一个优化：如果剩余的重量已经小于最轻的物品，则提前退出循环，这样可以减少无用的比较次数。
2. 未初始化变量 `r`
在你的代码中， `r` 表示当前选取的总价值，但没有被初始化为 0 ，所以可能输出错误结果。正确的写法是将其初始化为 0 sfqxx 发表于 2023-5-7 12:34
你点进去发表帖子旁边有个发布悬赏
？？在哪你截个图 陈尚涵 发表于 2023-5-7 12:36
？？在哪你截个图
https://t3.wodetu.cn/2023/05/07/c252dabecd6b1d866881da16376a0c21.png 陶远航 发表于 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
已经发的改不了了？ 陈尚涵 发表于 2023-5-7 12:45
已经发的改不了了？
是的 #include<bits/stdc++.h>
using namespace std;
struct Node
{
int m,v;
}a;
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.m,&a.v);
sort(a,a+n,cmp);//按单位价格降序排序
double sum=0;
for(int i=0;i<n;i++)
{
if(t>=a.m)//背包能放下整堆金币
{
t-=a.m;//背包容量减少
sum+=a.v;
}
else//不能放下整堆金币
{
sum+=1.0*a.v/a.m*t;//将背包装满
break;
}
}
printf("%.2f\n",sum);
return 0;
}
陶远航 发表于 2023-5-7 12:56
这个是题解？ 陈尚涵 发表于 2023-5-7 12:57
这个是题解？
嗯 题解有什么用？抄了会被封号 贪心 , 把 单价最高 的先装
#include <bits/stdc++.h>
using namespace std;
int n, t;
struct coin{
double price, storage;
} coins;
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 = {q/p, p};
}
sort(coins + 1, coins + n + 1, cmp);
for(int i = 1; i <= n; i++){
if(coins.storage <= t){
ans += coins.price * coins.storage;
t -= coins.storage;
}
else{
ans += coins.price * t;
break;
}
}
cout << fixed << setprecision(2) << ans << endl;
return 0;
}
页:
[1]