Question

一道数学题

现在有三个水桶，编号分别为a,b,c。有三个人编号分别为m,n,k。三个水桶一开始分别有高度为h_a,h_b和h_c的水。现在让三个人往水桶里面注水。每一次，只能选择一个人往三个水桶里面注水。如果选择让m来注水，可以分别使A,B,C三个水桶中水的高度分别增加H_ma,H_mb和H_mc。同理，如果让n或者k来注水，可以使三个桶中的水增加H_na,H_nb,H_nc和H_ka,H_kb,H_kc。以上所有参数都是已知，而且不变的。问题就是，每一次应该如何选择让哪一个人来注水，才能用最少的次数，使三个水桶都被注满？

Answer 1

设f(a,b,c)为在水高a, b, c时，用最佳策略时预期的需要达到100,100,100的步数。现在列出计算f(a,b,c)的方程：
f(a,b,c) = 对于每个人的最小值(
(1-H_a)*(1-H_b)*(1-H_C)*f(a,b,c) （三个桶都倒霉了）
+H_a*(1-H_b)*(1-H_c)*f(a+1,b,c) （桶a灌上了水）
+(1-H_a)*H_b*(1-H_c)*f(a, b+1,c) （桶b灌上了水）
+...
+H_a*H_b*H_c*f(a+1,b+1,c+1) （桶a,b,c都灌上了水）
+1) （当前操作耗费一步）
一上一共八种情况(2*2*2=8)，其中第一种情况的(1-H_a)*(1-H_b)*(1-H_C)*f(a,b,c)可以移到等式左边和f(a,b,c)合并，其余的7种情况用现有的值可以计算出来（下面解释）。对于每个人，计算出来候选的f(a,b,c)，再取那个f(a,b,c)最小的人，记录下来，并把f(a,b,c)的值记录下来用于后面的计算。

计算f(a,b,c)的方式是，首先，f(100,100,100) = 0. 然后注意到，上述方程的右边的所有f(i,j,k)都满足i+j+k > a+b+c. 所以只要我们按照a+b+c递减的顺序计算f(a,b,c)，那么方程右边的所有f(i,j,k)的值就已经计算完毕。

一共有101*101*101约等于100万个状态，对于计算机计算来说很小。
这和你上面提到的3^100的计算道理一样，但是使用了动态规划，因为决策树一共3^100个终点，但实际状态只有101^3个。

下面附计算和模拟的C++代码：

#include <iostream>
#include <ctime>
#include <cstdlib>
using namespace std;

double dp[128][128][128];
int decision[128][128][128];
double prob[3][3];

bool randomEvent(double probability){
if(rand()/double(RAND_MAX)<probability) return true;
return false;
}

int main(){

//input probabilities. prob[i][j] means the
//probability that person i adds 1cm to container j.
for(int i=0;i<3;i++) for(int j=0;j<3;j++)
cin>>prob[i][j];

//visit the states (i, j, k), where i, j, k are the
//heights of water in each of the three containers.
//We visit the states in decreasing order of i+j+k,
//because we always increase water height, so the
//expected number of operations at state (i, j, k)
//only depends on those with states (i, j, k) where
//i+j+k is greater.

for(int total=300; total>=0;total--)
for(int i=0;i<=100;i++)
for(int j=0;j<=100;j++)
{
int k = total - i - j;
if(k<0 || k>100) continue;

//we need 0 at the last step.
if(i==100 && j==100 && k==100) continue;
double bestresult;
int bestperson = -1;
for(int person = 0; person<3; person++)
{
//f(i,j,k) = rightside + coeff*f(i,j,k) + 1.
//(1-coeff)*f(i,j,k) = rightside + 1.
//let leftcoeff = 1-coeff.
double leftcoeff = 1;
double rightside = 1;
for(int fillA = 0; fillA<2; fillA++)
for(int fillB = 0; fillB<2; fillB++)
for(int fillC = 0; fillC<2; fillC++)
{
double probA = fillA?prob[person][0]:(1-prob[person][0]);
double probB = fillB?prob[person][1]:(1-prob[person][1]);
double probC = fillC?prob[person][2]:(1-prob[person][2]);
int newI = fillA?(i+1):i; if(newI>100) newI = 100;
int newJ = fillB?(j+1):j; if(newJ>100) newJ = 100;
int newK = fillC?(k+1):k; if(newK>100) newK = 100;
double totalProb = probA*probB*probC;
if(newI==i && newJ==j && newK==k) leftcoeff -= totalProb;
else rightside += totalProb * dp[newI][newJ][newK];
}
double thisresult = rightside / leftcoeff;
if(bestperson==-1 || thisresult < bestresult){
bestresult = thisresult;
bestperson = person;
}

}

dp[i][j][k] = bestresult;
decision[i][j][k] = bestperson;
}

srand(time(0));

//water heights to start with.
int ha, hb, hc;
cin>>ha>>hb>>hc;

//run a simulation.
int totalSteps = 0;
while(ha+hb+hc<300){
int person = decision[ha][hb][hc];
double expected = dp[ha][hb][hc];
cout<<"水高为"<<ha<<" "<<hb<<" "<<hc<<", "<<"选择第"<<(person+1)<<"人, "<<"预测"<<expected<<"步"<<endl;
if(randomEvent(prob[person][0])) ha++; if(ha>100) ha=100;
if(randomEvent(prob[person][1])) hb++; if(hb>100) hb=100;
if(randomEvent(prob[person][2])) hc++; if(hc>100) hc=100;
totalSteps++;
}
cout<<"共用了"<<totalSteps<<"步"<<endl;
}

使用时输入三个人得三个桶的值，然后输入水高起始值，比如：
0.2 0.3 0.4
0.5 0.1 0.3
0.1 0.6 0.2
0 0 0追问你好。很感谢你用心思考我的问题。
目前这个问题你的算法和代码都是正确的。
我一开始都搞错了，我本意是想举一个有3^101个状态的例子，而我提的这个问题一共就只有101^3个状态。

如果把水桶个数换成60个，灌水的人换成10个，麻烦你帮我看看有没有办法可以解。这个才是我的实际问题。我之前有考虑到MDP和动态规划，就是因为状态空间太大，我一直解决不了。
不管后面这个问题能不能解，我都很感谢你，也会选你的做最佳答案。

Answer 2

人：i=m,n,k; 桶 j=a,b,c 设桶的总高度为Hj，初始高度h_j,不同人注水一次的增加高度H_ij
正整数变量：注水次数 l ；
0，1变量：Xil 如果第 l 次注水选第 i 个人为1；否则0
数学模型：min l
约束：sum（（i ,l）, H_ij * Xil）>= Hj - h_j
l >0 取整数，Xil ：0，1变量

Answer 3

最优解的问题，次数肯定是整数，所以一定是三维坐标上的点，坐标值为整数，三个不等式方程组，按照等式求解，求解后可以不是整数，你可以取整 ，就可以等到最优解了....