1. 动态规划 备忘录法
备忘录方法采用自顶向下方式,为每个解过的子问题建立了备忘录以备需要时查看,避免了相同子问题的重复求解。
说明: 在非边界条件下,每次求解子问题时,先查找备忘录.
若子问题已经求解过了,直接取出子问题的解;若未求解过,则求解并保存到备忘录中.
此处的备忘录就是一个存储数据的容器.
/*
@author: jarg
@TODO 动态规划 - 备忘录法 求解二项式系数
*/
/* 求解二项式系数 */
public static int Binomial(int n,int m)
{
/* 边界条件 */
if(n==m || m==0)
{
return 1;
}
int date = readDate(n,m);
if(date>0)
{
/*
子问题已经计算过
读取保存在备忘录中的数据
*/
return date;
}
else
{
/*
子问题未计算过
解出子问题,将数据保存在备忘录中
*/
int result = Binomial(n-1,m) + Binomial(n-1,m-1);
writeDate(n,m,result);
return result;
}
}
/* 从备忘录中读取数据 */
public static int readDate(int n,int m)
{
for(int i=0;i<demo.size();i++)
{
Map<String,Integer> date = new HashMap<String,Integer>();
date = demo.get(i);
if(date.get("" + n + m) != null)
{
return date.get("" + n + m);
}
}
return 0;
}
/* 向备忘录中写入数据 */
public static void writeDate(int n,int m,int value)
{
Map<String,Integer> date = new HashMap<String,Integer>();
date.put("" + n + m,value);
demo.add(date);
}
2. 动态规划 迭代法:
迭代法采用自底向上方式,保存已求解的子问题,需要时取出,消除对某些子问题的重复求解.
Pascal三角形:
说明: 在非边界的情况下,二项式系数=上一行同列数值+上一行同列前一个数值.
为了节省空间,根据n的大小,定义长度为n+1的整型数组,用以存储子问题的解.
从后往前计算图中二项式系数的解,完成后,将问题解存储在数组中对应的列标号位置.
/*
@author: jarg
@TODO: 动态规划 - 求解二项式系数
*/
/* 求二项式系数 */
public static int binomial(int n, int m)
{
int value[] = new int[n+1];
for(int i=0;i<=n;i++)
{
value[i] = 1;
/* 边界条件m=0,n=m的情况 */
for(int j=i-1;j>0;j--)
{
value[j] = value[j] + value[j-1];
}
}
return value[m];
}
- 大小: 13.2 KB
- 大小: 35.6 KB
分享到:
相关推荐
C++下,分别使用递归和动态规划两种方法来实现求二项式的系数,避免了求阶乘的低效方法。
如题,动态规划法求解0-1背包问题实验报告 大二算法作业 使用java语言实现 内容框架:问题描述 思路分析 实例分析 实验原码及运行结果 实验心得
动态规划启发式算法求解时变车辆调度问题
计算机算法设计与分析动态规划法求解0-1背包问题的改进算法完整解释
算法作业-动态规划-投资收益最大化
lingo是求解最优问题的有效软件,不仅可以求一般的线性规划和非线性规划,还可以求无目标函数的动态规划问题,该论文给出了求解代码!
用动态规划法求解最大子段和问题 C语言实现
关于动态规划最短路径求解的matlab学习例子
用动态规划算法求解TSP,数据为Solomon数据集的c101文件读取,可视化路径图,用图展示每次迭代的最优值、最差值和平均值,并与Gurobi求解结果比较各计算时间下的目标值。动态规划算法求解TSP 用动态规划算法求解TSP...
经典算法问题-TSP商旅问题(Traveling Salesman Problem),它是数学领域中著名问题之一。...代码包含遗传算法和动态规划来求解这个问题,里面有完整源代码,并且有详细注释,还有两者的比较分析。
算法设计与分析实验2: 用C语言,采用动态规划算法解决TSP问题。资源:报告说明及完整源代码(源代码附在报告最后面)
最大子段和问题,可参考《算法设计与分析》讲义中关于用动态规划策略求解最大子段和问题的思想设计动态规划算法。本算法用户需要输入元素个数n,及n个整数。程序应该给出良好的用户界面,输出最大子段相关信息,包括...
动态规划求解资源分配,给定设备数与车间数,按照自动生成的利润表,求解得出最优分配。
实验一、Fibonacci数非递归解 ...请用递归方法和非递归方法求解该问题,各编写一个函数,要求函数接受 的值,返回 的值。两个程序实现后,分别求 的情况,对比两个程序的执行时间,然后分别对两种算法进行复杂性分析。
为了提高求解二次规划逆问题的速度,提出了针对求解该问题的非单调信赖域算法。为了降低问题的复杂度,将二次规划逆问题转换为决策变量相对较少的对偶问题,采用增广Lagrange法构造对偶问题的子问题,并通过引入光滑...
动态规划求解矩阵数乘问题,使得运行速度最快
论文研究-求解大规模VCVRP问题的快速动态规划算法.pdf, 车辆路径问题是一类典型的组合优化问题, 大部分研究都只考虑车辆能力固定的情形, 实际中受货物形状特性及客户...
目前对二维动态规划问题求解的matlab代码几乎没有,上传的为参考的一篇文献的代码并修改bug整理而成,包括主函数mindynprog1.m,和三个子函数DecisFun.m Stage_TransFun.m StageObjFun.m 以及命令空间输入的程序...