每天学一点算法-动态规划算法动态规划算法

133 阅读 0 评论 88 点赞

我是靠谱客的博主虚心帽子，这篇文章主要介绍每天学一点算法-动态规划算法动态规划算法，现在分享给大家，希望可以做个参考。

动态规划算法

定义

动态规划（Dynamic programming）是一种在数学、计算机科学和经济学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划常常适用于有重叠子问题和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。

　　动态规划背后的基本思想非常简单。大致上，若要解一个给定问题，我们需要解其不同部分（即子问题），再合并子问题的解以得出原问题的解。通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，从而减少计算量：一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。

　　关于动态规划最经典的问题当属背包问题。

步骤

1.最优子结构性质。如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质（即满足最优化原理）。最优子结构性质为动态规划算法解决问题提供了重要线索。

2. 子问题重叠性质。子问题重叠性质是指在用递归算法自顶向下对问题进行求解时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只计算一次，然后将其计算结果保存在一个表格中，当再次需要计算已经计算过的子问题时，只是在表格中简单地查看一下结果，从而获得较高的效率。

背包算法

简单背包问题

每种物品只有一个，各种物品组合的价值为20

代码

复制代码

public class Knapsack {  
   public static void main(final String... args) {  
       int[] arr = new int[5];  
       arr[0] = 11;  
       arr[1] = 8;  
       arr[2] = 7;  
       arr[3] = 5;  
       arr[4] = 3;  
       Knapsack k = new Knapsack();  
       System.out.println(k.knapsack(arr, 0, 20, 20));  
   }  
 
   /** 
    *@param arr    背包中的所有元素及其价值
    *@param start  放入背包的起始物品,当前要放入的物品
    *@param left   背包中剩余空间
    *@param sum    背包的总空间
    */  
   public boolean knapsack(int[] arr, int start, int left, int sum) {  
 
       if (arr.length == 0) {  
           return false;  
       }  
 
       // start from the next item in original array  
       if (start == arr.length) {  
           int[] tempArr = new int[arr.length - 1];  
           for (int i = 0; i < tempArr.length; i++) {  
               tempArr[i] = arr[i + 1];  
           }  
           return knapsack(tempArr, 0, sum, sum);  
       } else if (arr[start] > left) {  
           return knapsack(arr, start + 1, left, sum);  
       } else if (arr[start] == left) {  
           for (int i = 0; i < start + 1; i++) {  
               // print the answer out  
               System.out.print(arr[i] + "t");  
           }  
           return true;  
       } else {  
           return knapsack(arr, start + 1, left - arr[start], sum);  
       }  
   }  
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
public class Knapsack {  
   public static void main(final String... args) {  
       int[] arr = new int[5];  
       arr[0] = 11;  
       arr[1] = 8;  
       arr[2] = 7;  
       arr[3] = 5;  
       arr[4] = 3;  
       Knapsack k = new Knapsack();  
       System.out.println(k.knapsack(arr, 0, 20, 20));  
   }  
 
   /** 
    *@param arr    背包中的所有元素及其价值
    *@param start  放入背包的起始物品,当前要放入的物品
    *@param left   背包中剩余空间
    *@param sum    背包的总空间
    */  
   public boolean knapsack(int[] arr, int start, int left, int sum) {  
 
       if (arr.length == 0) {  
           return false;  
       }  
 
       // start from the next item in original array  
       if (start == arr.length) {  
           int[] tempArr = new int[arr.length - 1];  
           for (int i = 0; i < tempArr.length; i++) {  
               tempArr[i] = arr[i + 1];  
           }  
           return knapsack(tempArr, 0, sum, sum);  
       } else if (arr[start] > left) {  
           return knapsack(arr, start + 1, left, sum);  
       } else if (arr[start] == left) {  
           for (int i = 0; i < start + 1; i++) {  
               // print the answer out  
               System.out.print(arr[i] + "t");  
           }  
           return true;  
       } else {  
           return knapsack(arr, start + 1, left - arr[start], sum);  
       }  
   }  
}