织梦cms 5.6网站地图,图标怎么在wordpress,淘宝如何提升关键词排名,网上营销动态规划#xff1a; 所有的数据结构与算法的理解必须建立在题目的练习上#xff0c;否则看多少理论都没有实际用处#xff01;#xff01;#xff01;所以下面这些理论文字看不懂通通没关系#xff0c;跟随下面的背包问题还会跟深入的理解。一、基本概念#xff1a;任何…
动态规划
所有的数据结构与算法的理解必须建立在题目的练习上否则看多少理论都没有实际用处 所以下面这些理论文字看不懂通通没关系跟随下面的背包问题还会跟深入的理解。一、基本概念任何数学递推公式都可以直接转换成递归算法但是基本现实是编译器常常不能正确对待递归算法结果导致低效的程序。当怀疑很可能是这种情况是我们必须给编译器提供一些帮助将递归算法重新写成非递归算法让后者把这些子问题的答案系统地记录在一个表内。利用这种方法的一种技巧叫做动态规划。根据《数据结构与算法分析--Java语言描述》原书第三版 中给动态规划DP的定义出自《数据结构与算法分析--Java语言描述》原书第三版 二、主要分类动态规划一般可分为线性动规区域动规树形动规背包动规四类。 举例 线性动规拦截导弹合唱队形挖地雷建学校剑客决斗等 区域动规石子合并 加分二叉树统计单词个数炮兵布阵等 树形动规贪吃的九头龙二分查找树聚会的欢乐数字三角形等 背包动规01背包问题完全背包问题分组背包问题二维背包装箱问题挤牛奶等 除此之外还有许多变形的动态规划问题再次不一一列举。 三、动态规划问题中的术语这一部分看不懂没关系用处不大
阶段把所给求解问题的过程恰当地分成若干个相互联系的阶段以便于求解过程不同阶段数就可能不同。描述阶段的变量称为阶段变量。 状态状态表示每个阶段开始面临的自然状况或客观条件它不以人们的主观意志为转移也称为不可控因素。在具体题目中状态就是某阶段的出发位置它既是该阶段某路的起点同时又是前一阶段某支路的终点。 无后效性我们要求状态具有下面的性质如果给定某一阶段的状态则在这一阶段以后过程的发展不受这阶段以前各段状态的影响所有各阶段都确定时整个过程也就确定了。状态的这个性质意味着过程的历史只能通过当前的状态去影响它的未来的发展。 决策一个阶段的状态给定以后从该状态演变到下一阶段某个状态的一种选择行动称为决策。在最优控制中也称为控制。因状态满足无后效性故在每个阶段选择决策时只需考虑当前的状态而无须考虑过程的历史。 策略由每个阶段的决策组成的序列称为策略。集合中达到最优效果的策略称为最优策略。
最优化原理:作为整个过程的最优策略它满足相对前面决策所形成的状态而言余下的子策略必然构成“最优子策略”。一个问题满足最优化原理也称其拥有最优子结构性质。最优性原理实际上是要求问题的最优策略的子策略也是最优。 四、基本思想动态规划思想通常用于求解具有某种最优性质的问题。在这类问题中可能会有许多可行解。其基本思想也是将待求解问题分解成若干个子问题先求解子问题然后从这些子问题的解得到原问题的解。但是适合于用动态规划求解的问题经分解得到子问题往往不是互相独立的。如果我们能够保存已解决的子问题的答案而在需要时再找出已求得的答案这样就可以避免大量的重复计算。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到只要它被计算过就将其结果填入表中。 五、解题思路
1.找出最优解的性质刻画其结构特征和最优子结构特征 2.递归地定义最优值刻画原问题解与子问题解间的关系找到状态方程 3.以自底向上的方式计算出各个子问题最优解并避免子问题的重复计算 4.根据计算最优值时得到的信息构造最优解。 01背包
问题描述有N件物品和一个容量为C的背包。第i件物品的体积是v[i]价值是w[i]。求解将哪些物品装入背包可使价值总和最大。 从这个题目中可以看出01背包的特点就是每种物品仅有一件可以选择放或不放。
输入第一行两个数据物品件数N背包容量C
接下来N行每行对应第i件物品的体积v[i]和价值w[i]
Input
3 9
1 2
2 3
3 1
Output
6 思路一逆向规划
我们假定当前阶段的状态d(i, j)表示当前第i层将从第i个到第n个物品装入容量为j的背包所能达到的最大重量
由此规划的终点就是d(1, c)[即代表将第12,3...n个物品装入容量为G的背包中所能达到的最大重量]
规划的起点就是d(n, 0) 或 d(n, c)
如果我们不放物品i状态转移为d(i1, j)即将物品i1放入剩余容量仍为j的背包中的价值
如果我们放入物品i状态转移为d(i1, j-v[i])w[i], 即将物品i1放入剩余容量为j-v[i]的背包中的价值
状态转移方程d(i, j) max{d(i1, j), d(i1, j-v[i]) w[i]} import java.util.Scanner;public class Main {static Scanner in new Scanner(System.in);static int[] v,w;static int[][] d;static int n, c;public static void main(String[] args) {n in.nextInt();c in.nextInt();v new int[n1];w new int[n1];d new int[n2][c1];for (int i 1; i n; i) {v[i] in.nextInt();w[i] in.nextInt();}for(int i n; i 1; i--) {for(int j 0; j c; j) {d[i][j] (in ? 0 : d[i1][j]);if(j v[i]) {d[i][j] Math.max(d[i][j],d[i1][j-v[i]]w[i]);}}}System.out.println(d[1][c]);}
}思路二正向规划 我们假定当前阶段的状态d(i, j)表示当前第i层将前i个物品装入容量为j的背包所能达到的最大重量 规划的起点d(1, 0) 或 d(1, c) 规划的终点d(n ,c) 状态转移方程d(i, j) max{d(i-1, j), d(i-1, j-v[i]) w[i]} import java.util.Scanner;public class Main {static Scanner in new Scanner(System.in);static int[] v,w;static int[][] d;static int n, c;public static void main(String[] args) {n in.nextInt();c in.nextInt();v new int[n1];w new int[n1];d new int[n1][c1];for(int i 1; i n; i) {int v in.nextInt();int w in.nextInt();for(int j 0; j c; j) {d[i][j] (i1 ? 0 : d[i-1][j]);if(j v) {d[i][j] Math.max(d[i][j],d[i-1][j-v]w);}}}System.out.println(d[n][c]);}
}思路一与思路二区别1. 正向规划可以在输入v, w的过程中处理数据节省空间在打印结果的时候不方便2. 逆向规划可以保证打印结果时最小字典序需要存储v, w下面引入一个概念滚动数组形态上是一个一维数组其作用在于可以优化空间主要应用在递推或动态规划中尤其是在背包问题中。由于DP题目是一个自底向上的扩展过程我们常常需要用到的是连续的解当一个状态转移到另一个状态时大多数情况下之前存储的状态信息已经无用了往往可以舍去。所以用滚动数组优化是很有效的。好处利用滚动数组可以在N很大的情况下达到压缩存储的作用。滚动数组在时间上并没有什么改善但是能节省很大的空间。不足由于没有存储之前的数据所以在实现打印方面十分困难 思路三用滚动数组实现 我们假定当前阶段的状态d(j)表示将当前物品装入容量为 j 的背包所能达到的最大重量 规划的起点d( 0 ) 规划的终点d( c ) 状态转移方程d( j ) max{d( j ), d( j - v) w}
import java.util.Scanner;public class Main {static Scanner in new Scanner(System.in);static int[] v, w, d;static int n, c;public static void main(String[] args) {n in.nextInt();c in.nextInt();v new int[n1];w new int[n1];d new int[c1];for (int i 1; i n; i) {int v in.nextInt();int w in.nextInt();for (int j c; j 0; j--) {if (j v) {d[j] Math.max(d[j], d[j-v] w);}}}System.out.println(d[c]);}
} 注意在这类求最优解的背包问题中有的题目要求“恰好装满背包”时的最优解而有的题目则并没有要求必须装满。
区别这两种问法的实现方法是在初始化的时候有所不同。
如果是要求恰好装满背包那么在初始化时除了f[0]为0其它f[1..V]均设为-∞这样就可以保证最终得到的f[N]是一种恰好装满背包的最优解。 如果并没有要求必须把背包装满而是只希望价格尽量大初始化时应该将
f[0..V]全部设为0。为什么呢可以这样理解初始化的f数组事实上就是在没有任何物品可以放入背包时的合法状态。如果要求背包恰好装满那么初始化时只有容量为0的背包可能被价值为0的物品“恰好装满”其它容量的背包尚且没有合法的解属于未定义的状态如果背包并非必须被装满那么初始化时任何容量的背包都有一个合法解即什么都不装。
