你好,这是道动态规划(dp)背包问题,用贪心策略是错误的,可以被卡;
以下给出一组hack数据
```
1000 2
999 1000
2 10
```
按您的贪心答案为1000,而正确答案为选择500个时间为2的草药,从而达到500*10=5000的更高价值
by Kevin_Lsy @ 2023-07-17 20:48:01
@[Kevin_Lsy](/user/359287) 奥,难怪,我说怎么回事,是贪心呀,谢谢dalao指导
by Michelle01 @ 2023-07-17 20:49:25
这个题应该是用动态规划来做啊,是一道背包问题的模板
你的思路是啥
附上AC code:
```cpp
#include<iostream>
#include<cstring>
using namespace std;
const int N=1e6+5;
int n,m,f[2][N],c[N],w[N],p;
int main(){
cin>>m>>n;
for (int i=1;i<=n;i++){
cin>>w[i]>>c[i];
}
p=0;
for (int i=1;i<=n;i++){
p^=1;
for (int j=0;j<=m;j++){
f[p][j]=f[p^1][j];
if (j>=w[i])
f[p][j]=max(f[p][j], f[p^1][j-w[i]]+c[i]);
}
}
cout<<f[p][m];
return 0;
}
```
by 违规用户名U930502 @ 2023-07-17 20:55:30
@[Tim0303](/user/930502) 确实啊,这题是01背包的模板题
by Kevin_Lsy @ 2023-07-17 20:56:21
我也是用贪心做的 dalao的数据测出来是对的;
但是全WA了qwq
by D_key_yg_stc @ 2023-07-18 11:23:27
代码;
```c
#include<bits/stdc++.h>
using namespace std;
int t,m;
const int N=1e3;
struct med{
int a,b;
};
med M[N];
bool cmp(med A,med B){
return A.b*B.a>A.a*B.b;
}
int ans;
int d[N][N];
signed main(){
ios::sync_with_stdio(false);
//cin.tie(nullptr),cout.tie(nullptr);
cin>>t>>m;
for(int i=1;i<=m;i++){
cin>>M[i].a>>M[i].b;
}
sort(M+1,M+m+1,cmp);
for(int i=1;i<=m;i++){
while(t-M[i].a>=0){
if(t>=M[i].a){
t-=M[i].a;
ans+=M[i].b;
}
}
if(t==0){
break;
}
}
cout<<ans;
return 0;
}
```
by D_key_yg_stc @ 2023-07-18 11:26:48