Analysis
今天考试，$Mr.Yu$疯狂暗示，难道不是递增的哦
所以说我一来就开始看第三题，显示贪心错了大样例，然后就决定$dp$了，想不到居然对了，开心。
后面到网上来看题解，全部都是0/1分数规划，我震惊了，嗯，想不到啊。
这里来谈一谈我的做法，设$f[i]$表示才艺之的总之为$i$的时候最小的重量是多少，之所以要这么来设计是因为才艺值是固定的，重量值越小的时候，才艺值就越大，然后每一头奶牛只能够选一次，那么不就是一个0/1背包的模板题，最后来扫一遍得到答案吗
Codes
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
|
#include<bits/stdc++.h>
#define maxn 255
#define inf 1e-6
using namespace std;
struct cow{
int w;
int t;
}fj[maxn];
int f[maxn*1000];
int N,W;
int main(){
freopen("show.in","r",stdin);
freopen("show.out","w",stdout);
scanf("%d%d",&N,&W);
int maxt=0;
for(register int i=1;i<=N;i++){
scanf("%d%d",&fj[i].w,&fj[i].t);
maxt+=fj[i].t;
}
memset(f,0x3f,sizeof(f));
f[0]=0;
for(register int i=1;i<=N;i++){
for(register int j=maxt;j>=fj[i].t;j--){
f[j]=min(f[j],f[j-fj[i].t]+fj[i].w);
}
}
double ans=0;
for(register int i=1;i<=maxt;i++){
if(f[i]>=W)ans=max(ans,i/(f[i]+0.0));
}
ans*=1000;
printf("%d",(int)ans);
fclose(stdin);
fclose(stdout);
return 0;
}
|