题目描述
blablabla
样例
blablabla
算法1
非正解,使用随机化贪心,骗80–90分,这是没学dp的最好解决此种问题方法-------------
(暴力枚举) $O(懒得算)$
#include<iostream>
#include<cmath>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<cctype>
#include<cfloat>
#include<climits>
#include<iomanip>
#include<sstream>
#include<fstream>
#include<cstdlib>
#include<stack>
#include<queue>
#include<deque>
#include<map>
#include<set>
#include<vector>
#include<ctime>
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<n;++i){
totalv-=b[i].v;
if(totalv<0)break;
else totalw+=b[i].w;
}
return totalw;
}
int main(){
srand(time(0));
int n,v;
scanf("%d%d",&n,&v);
for(int i=0;i<n;++i){
a[i].autoi();
}
int max=-1;
for(int i=0;i<209999;++i){
mr(a,n);
int c=work(a,n,v);
if(c>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
```
代码的前后需要加上```才可以正常显示哈~
thanks
加油!
另外 题目描述、样例、算法2等部分如果没有内容的话,可以直接删掉~ 最终效果可以参考 AcWing 13. 找出数组中重复的数字
你这什么鬼
随机化贪心