动态规划k乘积问题.doc

《动态规划k乘积问题.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、.西安邮电大学（计算机学院）课实验报告实验名称：动态规划k乘积问题专业名称：班级：学生：学号（8位）：指导教师：实验日期：2016年月日..一.实验目的及实验环境实验目的:熟悉并掌握贪心算法实验环境:windows7vc6.0编译器二.实验容题目描述:设I是一个n位十进制整数。如果将I划分为k段，则可得到k个整数。这k个整数的乘积称为I的一个k乘积，试设计一个算法，对于给定的I和k，求出I的最大k乘积。算法设计:对于给你定的I和看k，计算I的最大k乘积问题。数据输入:由文件input.txt提取输入数据。文件的第1行中有2个正整数n和k。正整数n是

2、序列的长度，正整数k是分割的段数。在接下来的一行中是一个n位十进制整数。结果输出:将计算计算结果输出到文件output.txt，文件第一行中的数是计算出的最大k乘积。三．方案设计1.   分析最优解的结构为了方便起见，设I(s,t)是I的由s位开始的t位数字组成的十进制数，R(i,j)表示I(0,i)的j乘积。第j段的起始位置为第w位,1＜w≤j。则有如下关系R(i,j)=R(i,j-1)×I(w,j-w)      要使R(i,j)最大，则R(i,j-1)也是最大，所以最大Ｋ乘积问题的最优解包含其子问题的最优解。2.   建立递归关系设MaxI[

3、i][j]表示I(0,i)的最大j乘积，则原问题的最优值为MaxI[n][k]。当k＝1时，MaxI[n][1]=I(0,n);当k≠1时，可利用最优子结构性质计算MaxI[n][k], 若计算MaxI[n][k]的第k段的起始位置为第w位，1＜w≤j，则有MaxI[n][k]=MaxI[w][k-1]×I(w,n-w)。由于在计算时并不知道第k段的起始位置w，所以w还未定。不过w的值只有n-k+2种可能，即k-1≤w≤n。所以MaxI[n][k]可以递归地定义为  I(0,n)                               k＝1M

4、axI[n][k]=max  MaxI[w][k-1]×I(w,n-w)           k≠1 MaxI[n][k]给出了最优值，同时还确定了计算最优的断开位置w，也就时说，对于这个w有     MaxI[n][k]=MaxI[w][k-1]×I(w,n-w)若将对应于MaxI[n][k]的断开位置w记为demarcation[n][k]后，可递归地由 demarcation[n][k]构造相应的最优解。四．测试数据及运行结果..正常测试数据（3组）及运行结果；输入5位的数，分成3段输入6位的数，分6段..五．总结1．实验过程中遇到的问题及解

5、决办法；2．对设计及调试过程的心得体会。六．附录：源代码（电子版）#include#include#include#defineMAXN51#defineMAXK10//m[i][j]表示1~i十进制位分成j段所得的最大乘积longm[MAXK][MAXN]={{0,0}};//w[i][j]表示i~j十进制位所组成的十进制数longw[MAXN][MAXN]={{0,0}};intleaf[MAXN][MAXN]={{0,0}};voidmaxdp(intn,intk,int*a){int

6、i,j,d;longtemp,max;for(i=1;i<=n;i++){//分成一段m[i][1]=w[1][i];}for(i=2;i<=n;i++){//DP过程..for(j=2;j<=k;j++){max=0;for(d=1;dmax){max=temp;leaf[i][j]=d;}}m[i][j]=max;

7、printf("");}}printf("");for(i=1;i<=n;i++){for(j=1;j<=n;j++){printf("%ldt",m[i][j]);}printf("");}printf("");for(i=1;i<=n;i++){for(j=1;j<=n;j++){printf("%ldt",leaf[i][j]);}printf("");}}//输出分割后的K个数voidprint_foot(int*data,intn,intk){intd,i;intstack[256];inttop=0;inttmp

8、;tmp=n;while((tmp=leaf[tmp][k])>0){..stack[top++]=tmp;k--;}pr