贪心算法和动态规划（Java实现） 贪心算法和动态规划.pdf

"贪心算法和动态规划（Java实现）" 贪心算法是一种常用的算法设计策略，它所做出的选择总是当前看来是最好的。贪心算法的设计关键是选择贪心策略，且必须具备无后效性，即某个状态以后的过程不会影响以前的状态，只与当前状态有关。 贪心算法的解题步骤包括： 1. 将原问题分解为子问题； 2. 找出贪心策略； 3. 得到每个子问题的最优解； 4. 将所有的局部最优解的集合构成原问题的一个解。 需要注意的是，贪心算法不是对所有问题都能得到整体最优解，选择的贪心策略必须具备无后效性。一般来说，贪心算法会结合排序，即首先通过排序的方式处理数据。 在实际应用中，贪心算法可以解决很多问题，例如合并果子的问题。现在有n堆果子，第i堆有Ai个果子。现在要把这些果子合并成一堆，每次合并的代价是两堆果子的总果子数。求合并所有果子的最小代价。 在Java中，我们可以使用优先队列来实现贪心算法。我们将所有的果子数加入优先队列，然后不断地从队列中取出两个最小的元素，合并它们，并将合并的结果加入队列中。我们将所有的果子合并成一堆，并计算出合并的代价。 ```java //模拟6堆果子 int[] fruit = {5,8,3,2,6,1}; //合并果子 public int together_fruit(int[] fruit){ //使用优先队列存储果子 Queue<Integer> queue = new PriorityQueue<>(); for(int i=0;i<fruit.length;i++){ queue.add(fruit[i]); } //合并n堆果子需要有n-1次合并 int times = queue.size()-1; //用于存储每次合并耗费的体力 int count = 0; while(times-->0){ //每次出队两个元素，将两个元素的和入队 int A = queue.poll(); int B = queue.poll(); queue.add(A+B); count += (A + B); } return count; } ``` 动态规划算法是通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推（或者说分治）的方式去解决。动态规划算法的基本思想与分治法类似，也是将待求解的问题分解为若干个子问题（阶段），按顺序求解子阶段，前一个子问题的解，为后一个子问题的求解提供了有用的信息。在求解任一个子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解。 在实际应用中，动态规划算法可以解决很多问题，例如磁带的最优存储问题。分析：由上图中的读取程序i所需的时间tr我们可以看出，要读某个程序i，则读取程序i花费的时间是读取它前面的所有程序需要的时间加上读取它本身的时间。而一个程序本身的读取时间由这个程序的长度和频率决定，由上图我们知道这个关系是t = PL。故我们需要把每个程序PL计算出来，代表这个程序的读取时间，记为Ts（s为实际的意思）。在操作系统的进程调度中我们知道短作业优先的调度方式，各进程的平均周转时间最短。故这道题很有可能是将Ts按照从小到大的顺序排列，能够使平均读取时间达到最短。 ```java //磁带的最优存储问题 public int tapeStorage(int[] programs){ //将程序按照读取时间从小到大排序 Arrays.sort(programs); //使用动态规划算法解决问题 int[] dp = new int[programs.length]; dp[0] = programs[0]; for(int i=1;i<programs.length;i++){ dp[i] = dp[i-1] + programs[i]; } return dp[programs.length-1]; } ``` 贪心算法和动态规划算法都是常用的算法设计策略，它们可以解决很多实际问题。但是，贪心算法不是对所有问题都能得到整体最优解，选择的贪心策略必须具备无后效性。动态规划算法则可以解决很多问题，但是需要注意避免重复计算。