题目描述
blablabla
样例
blablabla
算法1
非正解,使用随机化贪心,骗80–90分,这是没学dp的最好解决此种问题方法-------------
(暴力枚举) $O(懒得算)$
include[HTML_REMOVED]
include[HTML_REMOVED]
include[HTML_REMOVED]
include[HTML_REMOVED]
include[HTML_REMOVED]
include[HTML_REMOVED]
include[HTML_REMOVED]
include[HTML_REMOVED]
include[HTML_REMOVED]
include[HTML_REMOVED]
include[HTML_REMOVED]
include[HTML_REMOVED]
include[HTML_REMOVED]
include[HTML_REMOVED]
include[HTML_REMOVED]
include[HTML_REMOVED]
include[HTML_REMOVED]
include[HTML_REMOVED]
include[HTML_REMOVED]
include[HTML_REMOVED]
using namespace std;
struct bag{
int v,w;
double i;
inline void autoi(){
scanf(“%d%d”,&v,&w);
i=1.0*w/v;
}
}a[3000];
inline bool cmp(bag x ,bag y){
return x.i >y.i ;
}
inline void mr(bag b[],int n){
sort(b,b+n,cmp);
for(int i=0;i<10;++i){
swap(b[rand()%n],b[rand()%n]);
}
}
inline int work(bag b[],int n,int v){
int totalv=v,totalw=0;
for(int i=0;i[HTML_REMOVED]max)max=c;
}
printf(“%d\n”,max);
//cout<<rand()<<" "<<rand()<<endl;
}
/
30 300
11 19
52 149
7 16
82 116
5 3
84 125
10 25
37 60
35 51
31 53
44 48
89 244
46 60
54 159
28 41
29 80
100 267
13 8
41 21
62 168
24 63
89 133
15 45
2 1
37 107
48 24
93 248
99 85
72 209
60 173
/
//output 867
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla