MOOC清华《程序设计基础》第6章：橱窗插花问题（动态规划，输出方法二）

MOOC清华《程序设计基础》第6章：橱窗插花问题（动态规划，输出方法二）

#include <iostream>
using namespace std;int V = 5;
int F = 3; int main()
{//定义美感数组int beauty[V][F] = {{7,5,-21},{23,21,5},{-5,-4,-4},{-24,10,-20},{16,23,20}};//定义最大美感得分和、相应方案int best_beauty = 0;//定义最优部分美感和数组，设定递推初值int best_partial[V + 1][F + 1] = {{0}};  //注意二维数组的赋零值方法 //定义记录新花瓶是否插花的数组bool put[V + 1][F + 1] = {{false}};  //输出方法二 //按 m 个花瓶插 n 朵花递推 for(int m = 1; m <= V; m++)for(int n = 1; n <= m && n <= F; n++){//默认新花瓶插花更优 best_partial[m][n] = best_partial[m - 1][n - 1] + beauty[m - 1][n - 1];put[m][n] = true;  //输出方法二 if(n < m && best_partial[m][n] < best_partial[m - 1][n])//若新花瓶不插花更优 {best_partial[m][n] = best_partial[m - 1][n];put[m][n] = false;  //输出方法二 }}//输出答案cout << "最大美感得分和：" << best_partial[V][F] << endl;cout << "插花方法：";for(int m = V, n = F; m >= 1;  )  //输出方法二，这里是逆序输出，因为本题逆序计算量小 if(put[m][n]){cout << n;m--;n--;}else{cout << '0';m--;}return 0;
}

在用动态规划算法解题时，输出方式也要考虑进来，简洁的输出方案将省去一些函数，让代码更简单。这也是一种优化。