基本上,这个问题模拟如下:
有一个装有50个绿球和50个红球的盒子。
我可以按以下规则从盒子中取出球,不放回:每次取出一个红球,我就损失一美元;每次取出一个绿球,我就赚一美元。
我可以随时停止取球。最坏的情况是我取出了所有100个球,净赚0美元。
问题是要想出一种最优的停止策略,并创建一个程序来计算该策略的预期价值。
我的策略是在预期再取一个球的价值为正数时继续取球。
也就是说,停止规则是动态的。
用Latex表示,下面是递归公式的图像:
http://i.stack.imgur.com/fnzYk.jpg
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
double ExpectedValue(double, double);
double max(double, double);
main() {
double g = 50;
double r = 50;
double EV = ExpectedValue(g, r);
printf ("%f\n\n", EV);
system("PAUSE");
}
double ExpectedValue(double g, double r){
double p = (g / (g + r));
double q = 1 - p;
if (g == 0)
return r;
if (r == 0)
return 0;
double E_gr = max ((p * ExpectedValue (g - 1, r)) + (q * ExpectedValue (g, r - 1)), (r - g));
return E_gr;
}
double max(double a, double b){
if (a > b)
return a;
else return b;
}
我让它运行了30分钟,它仍在工作。对于较小的g和r值,解决方案可以非常快地计算出来。我做错了什么吗?
非常感谢任何帮助!