西安邮电大学
（计算机学院）
课内实验报告
实验名称：动态规划k乘积问题
专业名称：
班级： 学生姓名：
学号（8位）： 指导教师：
实验日期：2016年月日
一. 实验目的及实验环境
实验目的: 熟悉并掌握贪心算法 实验环境: windows7 vc6.0编译器
二. 实验内容 题目描述:
设I是一个n位十进制整数。如果将I划分为k段，则可得到k个整数。这k个整数的乘积称为I的一个k乘积，试设计一个算法，对于给定的I和k，求出I的最大k乘积。 算法设计:
对于给你定的I和看k，计算I的最大k乘积问题。 数据输入:
由文件input.txt 提取输入数据。文件的第1行中有2个正整数n和k。正整数n是序列的长度，正整数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[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＝1
MaxI[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．实验过程中遇到的问题及解决办法； 2．对设计及调试过程的心得体会。
六．附录：源代码（电子版）
#include
//m[i][j]表示1~i十进制位分成j段所得的最大乘积 long m[MAXK][MAXN]={{0,0}} ;
//w[i][j]表示i~j十进制位所组成的十进制数 long w[MAXN][MAXN]={{0,0}} ; int leaf[MAXN][MAXN] = {{0,0}};
void maxdp(int n,int k,int *a) { int i,j,d; long temp,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; d < i ; d++){ //Test printf(\-----------\ if ( (temp = m[d][j-1]*w[d+1][i]) > max){ max = temp ; leaf[i][j]=d; } } m[i][j] = max ; printf(\ } } printf(\ for(i=1;i<=n;i++){ for(j=1;j<=n;j++){ printf(\ } printf(\
} printf(\ for(i=1;i<=n;i++){ for(j=1;j<=n;j++){ printf(\ } printf(\ } }
//输出分割后的K个数
void print_foot(int *data, int n, int k) { int d, i; int stack[256]; int top = 0; int tmp; tmp = n; while ((tmp = leaf[tmp][k]) > 0) { stack[top++] = tmp; k--; } printf(\ i = 1; while ((--top) >= 0) { tmp = stack[top]; for ( ; i <= tmp; i++) { printf(\ } printf(\ \ } for (; i <= n; i++) { printf(\ } printf(\ }
int main(void) { int n,k,i,j; int a[MAXN]={0},la=0; char c ; scanf(\ //input n, k while ( ( c=getchar() )!='#'){ //read integer a[++la] = c-'0' ; } for(i=1 ; i<= n; i++){ w[i][i]= a[i] ; for(j=i+1 ; j<= n; j++) w[i][j] = w[i][j-1]*10 + a[j] ; } for(i=1;i<=n;i++){ for(j=1;j<=n;j++){ printf(\ } printf(\ } maxdp(n,k,a) ; printf(\ print_foot(a, n, k); return 0; }