|
|
| |
|
| |
| |
| 资源分配（动态规划） |
|
[ 2008-8-31 16:55:00 | By: wantnon ] |
将编号为1~8的8名工人分配到编号主1~3的3个工区，效益矩阵如下表：
求效益最大的分配方案。
解：
转移方程：
前k个工区分配i个人的最大效益
=$max_{(i-j>=0),(j>=0):}$(前k-1个工区分配i-j个人的最大效益+第k个工区分配j个人的效益)
初值为：
前1个工区分配i(i=0~8)个人的最大效益=(0,5,15,40,80,90,95,98,100),(即表的第一行)
目标值为：
前3个工区分配8个人的最大效益
－－
c++程序：
＃i nclude<iostream.h>
struct Ver//二维指示向量
{
int x;
int y;
};
struct State//状态结构体
{
int prof;//累积利益
Ver foeStateVer;//指向前一状态
State();
};
State::State()
{
prof=0;
foeStateVer.x=0;
foeStateVer.y=0;
}
main()
{
int i,j,k;
int const Nzone=3;//工区数
int const Nworker=8;//工人数
int profMat[Nzone+1][Nworker+1]=
{
{0,0,0,0,0,0,0,0,0},
{0,5,15,40,80,90,95,98,100},
{0,5,15,40,60,70,73,74,75},
{0,4,26,40,45,50,51,52,73}
};//效益矩阵
State state[Nzone+1][Nworker+1];//状态空间
//初状态
for(i=0;i<=Nworker;i++)
{
state[1][i].prof =profMat[1][i];
}
//动态规划
for(k=2;k<=Nzone;k++)//按工区数推进(前k个工区)
{
for(i=0;i<=Nworker;i++)
{
for(j=0;j<=Nworker;j++)//尝试所有策略
{
if(i-j>=0&&state[k-1][i-j].prof+profMat[k][j]>state[k][i].prof)
{
state[k][i].prof =state[k-1][i-j].prof+profMat[k][j];
state[k][i].foeStateVer.x =k-1;
state[k][i].foeStateVer.y =i-j;
}
}
}
}
//回溯路径
Ver ver={Nzone,Nworker};
while(ver.x!=0&&ver.y!=0)
{
cout<<state[ver.x][ver.y].prof<<"<-";
ver=state[ver.x][ver.y].foeStateVer ;
}
}
运行结果：
140<-140<-80<-
即最优分配为：
第1工区4个人，
第2工区4个人，
第3工区0个人。
最大效益为140。
|
|
| | |
|
