目录
用蒙特卡罗算法模拟在线雇佣问题问题描述现实中的问题雇佣函数：全部代码：文章只供参考，如果有什么不对的地方会及时更正，学习也是一个分享的过程，希望和大家一起进步。
用蒙特卡罗算法模拟在线雇佣问题
问题描述
首先看看雇佣问题的基本内容。
假设你要雇佣一个新的办公室助理，雇佣代理每天向你推荐一个应聘者（连续推荐n个），你面试这个人，如果这个应聘者比目前的办公室助理更优秀，你就会辞掉当前的办公室助理，然后聘用这个新的。面试一个人需付给雇佣代理一笔费用，聘用办公助理也需要费用。
假设推荐费用为Ci，雇佣的费用为Ch，假设整个过程中雇佣了m次，于是总的费用是 nCi+mCh。由于n是固定值，总费用的变化取决于m值。
如果要费用最少，这时可以很容易的想到，只雇佣第一个人，即第一个人是最好的就只用花费n*Ci+Ch的费用。但是事前我们并不知道最好的那个人在哪。所以想要雇佣最好的办公室经理，一般的方法就是遍历所有的推荐者。
HIRE-ASSISTANT(n)best ← 0® candidate 0 is a least-qualified dummy candidatefor i ← 1 to ndo interview candidate iif candidate i is better than candidate bestthen best ← ihire candidate i
现实中的问题
但是现在，假设我们不希望面试所有的应聘者以找到最好的一个。我们也不希望因为有更好的申请者出现，不停雇佣新人解雇旧人。我们愿意雇用接近最好的应聘者，只雇用一次。我们必须遵守公司的一个要求：在每次面试后，或者必须立即提供职位给应聘者，或者拒绝。在最小化面试次数和最大化雇用应聘者的质量两方面如何取得平衡？就会出现一个概率问题：最好的那个人出现时的概率有多大和小标是多少？
这时就引入了我们需要解决的问题：最好的那个人出现的概率最大时 k 的取值和最大概率是多少呢？
首先，在面试一个应聘者之后，我们给每人一个分数。在面试过j个人之后，我们能知道这j个人中的最高分，但是不知道后面的n-j个会不会有最高的。所以我们决定采取下面的方法：
选择一个正整数k<n。面试然后拒绝前k个应聘者，再雇佣其后比前面的应聘者有更高分数的第一个应聘者，如果最高得分的应聘者在前k个应聘者，我们将雇佣第n个应聘者。
下面是伪代码：
c++代码如下：
产生随机数：
void random1(int list[100]){//初始化随机数的发生，使用时间函数并使其非负int a = 0, b = 100;int i = 100, r = 0;while (i) {r = rand() % (b - a + 1) + a; /*控制随机数的范围（简单记为：取“区间长度+1”的模再+前端点值）*/list[i-1] = r; //得到0到100的100个随机数 i--;}// 把list数组的r1,r2个元素改成100和99，保证list数组中一定有最好的和次好的那个人 int r1 = rand() % (b - a + 1) + a; int r2 = rand() % (b - a + 1) + a; list[r1] = 100; //把list数组的第r个元素改成100 list[r2] = 99; //把list数组的第r个元素改成99}
雇佣函数：
void hire_ass(int iter_time){int a[100];int list[100]={0};float key1=0;int x=0;for(int t=0;t<100;t++){float k=0;for(int i=0;i<iter_time;i++){random1(list); //调用random函数产生100个随机数的数组 int best=0;int best1=0;//找到0到t之间的最大值 for(int j=0;j<t;j++){if(list[j]>best){best = list[j];}}//找到t到100之间的第一个大于best的值 for(int j=t;j<100;j++){if(list[j]>best)best1 = list[j];}if(best1==100) //只求一个时 //if(best1==100 || best1==99) // 求两个最好的 k = k+1;}float key = k/iter_time;a[t] = key;if(key>key1){key1=key;x = t+1;}//cout<<key<<" ";}cout<<endl;cout<<"最好的概率和下标是："<<key1<<" "<<x<<endl;}
结果显示：
全部代码：
#include <iostream>#include<iostream>#include<ctime>//包含时间的头文件#include<cstdlib> //包含随机数函数的头文件#include <cmath>/* run this program using the console pauser or add your own getch, system("pause") or input loop */using namespace std;void random1(int *list);void hire_ass(int iter_time);int main(int argc, char** argv) {srand((unsigned)time(NULL)); //一定要写在循环的外面，或者循环调用的外面 int a,iter_time;cout<<"输入循环次数："<<endl;cin>>iter_time;//hire(iter_time);hire_ass(iter_time);return 0;}void random1(int list[100]){//初始化随机数的发生，使用时间函数并使其非负int a = 0, b = 100;int i = 100, r = 0;while (i) {r = rand() % (b - a + 1) + a; /*控制随机数的范围（简单记为：取“区间长度+1”的模再+前端点值）*/list[i-1] = r; //得到0到100的100个随机数 i--;}// 把list数组的r1,r2个元素改成100和99，保证list数组中一定有最好的和次好的那个人 int r1 = rand() % (b - a + 1) + a; int r2 = rand() % (b - a + 1) + a; list[r1] = 100; //把list数组的第r个元素改成100 list[r2] = 99; //把list数组的第r个元素改成99}void hire_ass(int iter_time){int a[100];int list[100]={0};float key1=0;int x=0;for(int t=0;t<100;t++){float k=0;for(int i=0;i<iter_time;i++){random1(list); //调用random函数产生100个随机数的数组 int best=0;int best1=0;//找到0到t之间的最大值 for(int j=0;j<t;j++){if(list[j]>best){best = list[j];}}//找到t到100之间的第一个大于best的值 for(int j=t;j<100;j++){if(list[j]>best)best1 = list[j];}if(best1==100) //只求一个时 //if(best1==100 || best1==99) // 求两个最好的 k = k+1;}float key = k/iter_time;a[t] = key;if(key>key1){key1=key;x = t+1;}//cout<<key<<" ";}cout<<endl;cout<<"最好的概率和下标是："<<key1<<" "<<x<<endl;}
