其实我一直在想一个问题,为什么我觉得学习计算机算法比高中的数学难?
记得高中的数学那是信手撵来(当然不是每一道题目),不谈学得有多好,但是起码对待每一道数学题都有自己的思路,想法,一般都能解出来,但是为什么学习计算机算法的时候就没有这种感觉呢。宏观上看过去第一眼肯定是计算机算法一般都是文字性表述,应该比高中的数学逻辑简单吧。但是,为什么学习计算机算法就感觉特别不自然。对于简单的题目套用简单的解法思路都好难实现出来,难道是我的脑袋退化了?
不过,客观上讲,大学课程,当然要比高中课程层次要高。
由于我看的是算法导论,所以讲的比较清楚(PS:翻译不说有多好,但是肯定会有晦涩的地方),关于高级的计算机算法设计中分为3类问题(按照书上划分的):动态规划,贪心算法,平摊分析。其实,计算机算法也有运筹学的内容,有关效率选择,最大价值等等。我能想到的应用就是什么主从节点的选择,考虑到最少的成本而获得最大计算机利用率之类的。我自然时根据书中的规划来学习的,首先接触的是动态规划。
在现实问题中,人们对于这样一类问题:在进行解的选择时,下一步的选择会影响到前面的选择而导致整个前面选择的解发生变化,这样,人们的脑袋可是想象不过来,递归的进行重新选择解(如果人的脑袋有很好的rom就好了);其实在没有接触贪心算法的时候,我们很擅长用这种思想解决问题,比如进行路程最短问题,我们总是会先选择我们能进行选择的路程试探,找到最短的路程,然后在进行下一步的选择,这是最简单的思想,所谓贪心算法。但是,就像我方才提到的,有些问题是不能通过“贪心”选择的,下面是一个方便的例子(书上太多例子了,不知道那一个最能说明问题):0-1背包问题;
小偷进入了一家首饰店,首饰店中每一件物品有且只有一件,共有n件,店中有太多的首饰,小偷看看他可怜的布袋,最多能装下体积为V的首饰,对于每一件首饰i,其价值为Wi,体积为Vi,所以,小偷要进行选择,选择在其布袋中能装下并且价值最大的一些首饰。(脚趾头想一想都知道,不能先选择价值最大的首饰,你们懂的~),貌似用高中排列组合的话,能取到是2的N次方种组合,而且还要考虑到体积最大问题,如果这个小偷有这种脑袋的话,他也算NB了(如果有,应该不用做小偷了),指数级的选择次数,计算机算法中它是低效的,那,我们现在来观察一下,有没有更好的办法。递归,貌似是很适合该类问题的,对于递归的解法,我们是要找到递归子,即对于每一个大问题,总有一个小问题能嵌于其中并且是递归嵌套的,0-1背包问题中,我们观察到,如果是在选择物品i时,其总价值最大并且体积不能超出,要么是在现在加入i物品后体积内除去该物品的最大价值,要么是在加入该物品后体积内包含该物品并且剩余体积内价值最大的物品组合。这是一个很难表述的解法,下面是一个函数式(其实时wiki上down的,有了它,好理解多了):
f[i][j]{
f[i-1,j] {j<Vi}
max{f[i-1,j],f[i-1,j-Vi]+Pi} {j>=Vi}
0 {i=0 OR j=0}
}
关键是中间一个式子,我们来看一个具体的例子:
体积分别为:{2,2,6,5,4}
价值分别为:{6,3,5,4,6}
现在,如果我们规定最大体积为6,我们直观看到如果我们选择第1,2件物品,体积为4,价值为9,如果我们继续添加,那么就超出了最大体积,现在,只能是在剩余的物品中替换现有的,首先考虑物品3,4,如果替换任意其中之一,那么将超出最大体积约束,再来看看物品5,体积为4,替换已有选择的物品中任意一件,不会破坏条件,那么,我们就来比较一下,如果替换了该物品,体积编程6,价值为12,大于9,但是,我们知道,现在体积变大了(原先是4),所以,我们还需要考虑在没有添加物品5之前,体积为6,并且最大价值最大的组合,貌似还是物品1,2的组合,价值为9,不大于现有价值12,那么,我们就可以成功添加该物品5。
下面是实现代码:
public class Bag_01{
static void bag_pro(int[] w,int v[],int maxWeight){
int[][] vw = new int[w.length][maxWeight+1];
for(int i=0;i<maxWeight+1;i++){
if(w[0]<=i){
vw[0][i] = v[0];
} else {
vw[0][i] = 0;
}
}
for(int i = 1;i<w.length;i++){
for(int j = 0;j<maxWeight+1;j++){
if(j<w[i]){
vw[i][j] = vw[i-1][j];
} else if(vw[i-1][j]<=(vw[i-1][j-w[i]]+v[i])){
vw[i][j] = vw[i-1][j-w[i]]+v[i];
} else {
vw[i][j] = vw[i-1][j];
}
}
}
for(int i = 0;i<w.length;i++){
for(int j = 0;j<maxWeight+1;j++){
System.out.print(vw[i][j]+" ");
}
System.out.print("\n");
}
}
public static void main(String args[]){
int w[] = {2,2,6,5,4};
int v[] = {6,3,5,4,6};
int maxWeight = 6;
bag_pro(w,v,maxWeight);
}
}
打印出来的是对每一规定最大体积内的体积逐步添加物品的最大价值的表;
上面的例子比较直观,用于动态规划的思路去解决问题,其思想就是找到一个可以递归的子问题,子问题的最优解即问题的最优解。这是我们思考问题的方式,递归使用于动态规划的寻找最优子问题结构,至于寻找子问题的解的结构,可以是迭代,也可以是递归。下面是“官方”步骤:
1.描述最优解结构;
2.递归定义最优解的值;
3.按自底向上的方式计算最优解的值;
4.由计算出的结果构造一个最优解;
当然,动态规划的最重要一点就是3,一定是自底向上求解过程,这样,才能运用到递归的子结构。通过子问题的最优解,得到问题的最优解。就像是背包问题,我们一定是求表中最后一列,最后一行的值,而该值是通过它的前列或者时前行得到的。
动态规划除了最优的子结构,还有一特征就是重叠的子问题,之所以动态规划能够缩减运行的时间,就是通过在以得到的子问题解中寻找值,而不是又一次计算,人脑之所以不能动态规划解决问题就是因为人脑没有那么一块地方保存先前计算的值,就算你记住了10个值,能记住100个?1000个?
最后,两点,重叠子问题,最优子结构,自底向上。
分享到:
相关推荐
利用动态规划算法,可以优雅而高效地解决很多贪婪算法或分治算法不能解决的问题。因此,动态规划技术越来越成为解决许多重要的应用问题的关键技术。例如,用动态规划解决0-1背包问题、图像数据压缩、矩阵连乘、有向...
北京工业大学--算法作业2--动态规划算法实现0-1背包问题---Java代码 利用动态规划算法实现0-1背包问题或装配线调度问题。(二选一) 要求测试数据以文本文件的形式存储, 即所有的数据由文本文件读入。 利用动态...
【达摩老生出品,必属...资源名:matlab实现动态规划算法 程序源码.zip 资源类型:程序源代码 源码说明: 基于matlab实现动态规划的程序,包含完整源码和注释,非常适合借鉴学习 适合人群:新手及有一定经验的开发人员
1.掌握动态规划算法的基本思想,包括最优子结构性质和基于表格的最优值计算方法。 2.熟练掌握分阶段的和递推的最优子结构分析方法。 3.学会利用动态规划算法解决实际问题。 题目一:数塔问题 给定一个数塔,其...
几道动态规划的经典算法 非常经典 值得分享
动态规划算法简介 动态规划算法很详细 有典型例子 适合初学者
《动态规划算法实验》实验报告
动态规划算法将原问题分解为若干个子问题,先求子问题的解,然后从这些子问题的解得到原问题的解。 这些子问题的解往往不是相互独立的。在求解的过程中,许多子问题的解被反复地使用。为了避免重复计算,动态规划...
利用动态规划算法解决图形图像处理问题,用Java编写,代码经过调试健壮性良好
动态规划算法实现投资问题,老师给的比较实用的,呵呵,希望大家多多采纳
动态规划算法与贪心算法动态规划算法与贪心算法动态规划算法与贪心算法动态规划算法与贪心算法动态规划算法与贪心算法动态规划算法与贪心算法动态规划算法与贪心算法
动态规划算法课件PPT,读者可以参考,非常不错的,清华老师的
0_1背包问题动态规划算法的探讨.pdf 0_1背包问题动态规划算法的探讨.pdf 0_1背包问题动态规划算法的探讨.pdf
动态规划算法(下).ppt动态规划算法(下).ppt动态规划算法(下).ppt
详细解释了动态规划算法的各种应用场合,对于做ACM题很有帮助
动态规划算法求解TSP 用动态规划算法求解TSP,数据为Solomon数据集的c101文件读取,可视化路径图,用图展示每次迭代的最优值、最差值和平均值,并与Gurobi求解结果比较各计算时间下的目标值。动态规划算法求解TSP 用...
动态规划算法 数据结构 算法导论 编程思想 程序员指定用书
c/c++语言的动态规划算法动态规划动态规划动态规划动态规划
本算法用于背包问题的动态规划算法,假设每种物品的数量是不限的,求最大体积为C时的所装最有价值物品。