/**
* 有一个 M x N 的矩阵,其中每个格子里面都有特定的钱。
* 左上角走到右下角,只能向右或者向下走,问怎么走才能捡到最多的钱。
* 输出捡钱的路径。
* 解析: 动态规划。 首先找到子结构,构造递推式。
* 对于每个位置能捡到的最多的钱是:
* a[i][j] = max{a[i-1][j] + w[i][j],a[i][j-1] + w[i][j]}
*/
#include <stdio.h>
#define M 5
#define N 4
int w[M][N]; //矩阵
int a[M][N]; //当前捡到的最大的钱的值
int path[M][N]; //记录路径,1表示从上面捡着钱下来,0表示从左边捡着钱过来
void find_path(){
int i,j;
a[0][0] = w[0][0];
//初始化左边界
for(i=0;i<M;i++){
a[i][0] = a[i-1][0] + w[i][0];
path[i][0] = 1;
}
//初始化右边界
for(j=0;j<N;j++){
a[0][j] = a[0][j-1] + w[0][j];
path[0][j] = 0;
}
//两个循环开始自底向上求解
for(i=1;i<M;i++){
for(j=1;j<N;j++){
int up = a[i-1][j] + w[i][j];
int left = a[i][j-1] + w[i][j];
if(up > left){
a[i][j] = up;
path[i][j] = 1;
}
else{
a[i][j] = left;
path[i][j] = 0;
}
}
}
}
int main(){
int tmp[M][N] = {{4,3,12,1},{11,7,4,2},{6,20,15,2},{4,5,8,1},{3,3,4,6}};
int i,j;
//初始化矩阵
for(i=0;i<M;i++)
for(j=0;j<N;j++){
w[i][j] = tmp[i][j];
}
printf("\n\n");
//自底向上求解
find_path();
//打印出路径以及每个位置能捡到的最多的钱数
for(i=0;i<M;i++){
for(j=0;j<N;j++)
printf("%5d(%d)",a[i][j],path[i][j]);
printf("\n");
}
return 0;
}
运行结果:
分享到:
相关推荐
动态规划求解矩阵数乘问题,使得运行速度最快
动态规划求解矩阵链乘
给定n个矩阵(A1,A2....An),其中Ai与Ai+1是可乘的,i=1,2,...,n-1.考察这n个矩阵的连乘积A1A2,...,An。 该资料为使用动态规划法解矩阵连乘积的最有计算次序问题,使用C++语言实现
最大子段和问题,可参考《算法设计与分析》讲义中关于用动态规划策略求解最大子段和问题的思想设计动态规划算法。本算法用户需要输入元素个数n,及n个整数。程序应该给出良好的用户界面,输出最大子段相关信息,包括...
关于动态规划最短路径求解的matlab学习例子
用动态规划法求解最大子段和问题 C语言实现
使用c#实现动态规划法——求解矩阵连乘问题,包括GUI和逻辑实现。
关于运用动态规划解决矩阵链乘法问题的具体步骤
最大子段和问题的动态规划求解最大子段和问题的动态规划求解最大子段和问题的动态规划求解最大子段和问题的动态规划求解
动态规划算法中矩阵连乘的实现代码,主要是用C语言编写;
主要介绍了Java矩阵连乘问题(动态规划)算法,结合实例形式分析了java实现矩阵连乘的算法原理与相关实现技巧,需要的朋友可以参考下
重点掌握:动态规划法求解每对结点之间的最短路径、0/1背包问题。 如果求任意两点之间的最短路径,两点之间可以直接到达但却不是最短的路径,要让任意两点(例如从顶点a点到顶点b)之间的路程变短,只能引入第三个点...
矩阵相乘问题的动态规划,动态规划是解决多阶段决策过程最优化问题的一种方法,其思想是将求解的问题一层一层地分解成一级一级的子问题,子问题的求解由繁到简逐步缩小,直到可以直接解出子问题为止。下面用动态规划...
算法设计与分析,使用动态规划法解决矩阵连乘问题。内有MatrixChain、TraceBack、RecurMatrixChain-递归解决矩阵连乘问题等程序,非常超值啊!
算法设计与分析课内实验——动态规划求单源最短路径。文档很齐全,包括算法分析过程和源代码(java语言eclipse环境)
JAVA版动态规划解决最短路径问题 啊
用动态规划算法求解TSP,数据为Solomon数据集的c101文件读取,可视化路径图,用图展示每次迭代的最优值、最差值和平均值,并与Gurobi求解结果比较各计算时间下的目标值。动态规划算法求解TSP 用动态规划算法求解TSP...
动态规划求解并输出所有LCS
应用动态规划算法思想求解矩阵连乘的顺序问题。 【实验性质】 验证性实验(学时数:2H) 【实验要求】 应用动态规划算法的最优子结构性质和子问题重叠性质求解此问题。分析动态规划算法的基本思想,应用动态规划策略...