分享
 
 
 

“插花问题”的动态规划法算法

王朝other·作者佚名  2007-09-29
窄屏简体版  字體: |||超大  

//:============================“插花问题”的动态规划法算法============================

#define F 100

#define V 100

/**//*

插花问题描述:

将f束鲜花插入v个花瓶中,使达到最徍的视觉效果,

问题相关约定及插花要求:

鲜花被编号为1--f,花瓶被编号为1--v,花瓶按从小到

大顺序排列,一只花瓶只能插一支花,鲜花i插入花瓶j中的

视觉效果效果值已知,编号小的鲜花所放入的花瓶编号也小

问题求解思路:

花瓶j(1<=j<=v)中插入鲜花的可能编号为[1..j](编号

小的鲜花所放入的花瓶编号也小);

设数组p[i][j]表示鲜花i插入花瓶j的好看程度,数组

q[i][j]表示[1..i]束鲜花插入[1..j]个花瓶所能得到的最大

好看程度,初始化q[0][0] = 0;q[0][j]=0(1<=j<=v),则q[f][v]

是问题的解.

特别地,j束鲜花插入到前面的j只花瓶中,所得到的好看

程度是q[j][j] = p[1][1]+p[2][2]+...+[j][j].现将插花过

程按花瓶排列顺序划分成不同阶段,则在第j阶段,第i束鲜花

若放入第j号花瓶,最大好看程度是q[i-1][j-1]+p[i][j];第i束鲜

花若放入前j-1个花瓶中的某一个,所得的好看程度是q[i][j-1],

那么在第j阶段,插入第i束鲜花所能得到的最大好看程度为:

q[i][j] = MAX(q[i-1][j-1]+p[i][j],q[i][j-1]),要使q[i][j]

最大,应使q[i-1][j-1]和q[i][j-1]也最大

*/

#define MAX(A,B) ((A) > (B) ? (A):(B)) //求取两数的最大值宏定义

#define F 100 //鲜花数最大值常量定义

#define V 100 //花瓶数最大值常量定义

//“插花问题”的初始化函数

// int f,v: 鲜花数量,花瓶个数

// int p[][v]: 鲜花i插入花瓶j的好看程度

void Flower_Initialize(int *f,int *v,int p[][V])

...{

int i,j;

printf("输入鲜花数量及花瓶个数:");

scanf("%d%d",f,v);

printf("顺序输入各鲜花插入各花瓶的好看程度: ");

for(i=1;i<=*f;i++)

for(j=1;j<=*v;j++)

p[i][j] = i*j;

//scanf("%d",&p[i][j]);

}

//“插花问题”的动态规划法解决函数

// int p[][v]: 鲜花i插入花瓶j的好看程度

// int f,v: 鲜花数量,花瓶个数

// int *way: 鲜花插入花瓶的插入方法结果

int Ikebana(int p[][V],int f,int v,int *way)

...{

int i,j,q[F][V],newv;

q[0][0] = 0; //初始化[没有一束花插入花瓶时],好看程度自然为0

//设置v个花瓶分别被插入v束鲜花时各号花瓶对应的(初始)最大好看程度

for(j = 1;j <= v;j++)

...{

q[0][j] = 0;

//设置第j束鲜花放入第j号花瓶中的最大好看程度

q[j][j] = q[j - 1][j - 1] + p[j][j];

}

for(j = 1;j <= v;j++)

for(i = 1;i < j;i++) //计算在第j阶段,插入第i束鲜花所能得到的最大好看程度

q[i][j] = MAX(q[i - 1][j - 1] + p[i][j],q[i][j - 1]);

newv = v;

for(i = f;i > 0;i--)

...{

while(q[i-1][newv-1]+p[i][newv] < q[i][newv])

newv--;

//确定鲜花i插在花瓶newv中,并准备考虑前一只花瓶

way[i] = newv--;

}

return(q[f][v]);

}

//测试“插花问题”的动态规划法函数

void Run_Ikebana()

...{

//循环计数器,鲜花数量,花瓶个数,鲜花i插入花瓶j的好看程度,鲜花插入花瓶的插入方法结果

int i,f,v,p[F][V],way[F];

Flower_Initialize(&f,&v,p);

printf("最大好看程度点数为%d ",Ikebana(p,f,v,way));

printf("插有鲜花的花瓶是: ");

for(i = 1;i <= f;i++)

printf("%4d",way[i]);

}

//:============================“插花问题”的动态规划法算法============================

int main(int argc, char* argv[])

...{

//Run_SubString();

Run_Ikebana();

printf(" 应用程序运行结束! ");

return 0;

}

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
2023年上半年GDP全球前十五强
 百态   2023-10-24
美众议院议长启动对拜登的弹劾调查
 百态   2023-09-13
上海、济南、武汉等多地出现不明坠落物
 探索   2023-09-06
印度或要将国名改为“巴拉特”
 百态   2023-09-06
男子为女友送行,买票不登机被捕
 百态   2023-08-20
手机地震预警功能怎么开?
 干货   2023-08-06
女子4年卖2套房花700多万做美容:不但没变美脸,面部还出现变形
 百态   2023-08-04
住户一楼被水淹 还冲来8头猪
 百态   2023-07-31
女子体内爬出大量瓜子状活虫
 百态   2023-07-25
地球连续35年收到神秘规律性信号,网友:不要回答!
 探索   2023-07-21
全球镓价格本周大涨27%
 探索   2023-07-09
钱都流向了那些不缺钱的人,苦都留给了能吃苦的人
 探索   2023-07-02
倩女手游刀客魅者强控制(强混乱强眩晕强睡眠)和对应控制抗性的关系
 百态   2020-08-20
美国5月9日最新疫情:美国确诊人数突破131万
 百态   2020-05-09
荷兰政府宣布将集体辞职
 干货   2020-04-30
倩女幽魂手游师徒任务情义春秋猜成语答案逍遥观:鹏程万里
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案神机营:射石饮羽
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案昆仑山:拔刀相助
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案天工阁:鬼斧神工
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案丝路古道:单枪匹马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:与虎谋皮
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:李代桃僵
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:指鹿为马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:小鸟依人
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:千金买邻
 干货   2019-11-12
 
推荐阅读
 
 
 
>>返回首頁<<
 
靜靜地坐在廢墟上,四周的荒凉一望無際,忽然覺得,淒涼也很美
© 2005- 王朝網路 版權所有