动态规划(Dynamic Programming)算法的核心思想是:将大问题划分为小问题进行解决,从而一步步获取最优解 的处理算法 。
与分治法不同的是,适合于用动态规划求解的问题,经分解得到子问题往往不是互相独立的。 ( 即下一个子 阶段的求解是建立在上一个子阶段的解的基础上,进行进一步的求解 ) 。
动态规划可以通过填表的方式来逐步推进,得到最优解。
动态规划算法最佳实践-背包问题
背包问题:有一个背包,容量为 4 磅 , 现有如下物品:
物品 |
重量 |
价格 |
吉他(G) |
1 |
1500 |
音响(S) |
4 |
3000 |
电脑(L) |
3 |
2000 |
(1)要求达到的目标为装入的背包的总价值最大,并且重量不超出
(2)要求装入的物品不能重复
总体思路
根据动态规划解题步骤(问题抽象化、建立模型、寻找约束条件、判断是否满足最优性原理、找大问题与小问题的递推关系式、填表、寻找解组成)找出01背包问题的最优解以及解组成,然后编写代码实现。
动态规划的原理
动态规划与分治法类似,都是把大问题拆分成小问题,通过寻找大问题与小问题的递推关系,解决一个个小问题,最终达到解决原问题的效果。但不同的是,分治法在子问题和子子问题等上被重复计算了很多次,而动态规划则具有记忆性,通过填写表把所有已经解决的子问题答案纪录下来,在新问题里需要用到的子问题可以直接提取,避免了重复计算,从而节约了时间,所以在问题满足最优性原理之后,用动态规划解决问题的核心就在于填表,表填写完毕,最优解也就找到。
最优性原理是动态规划的基础,最优性原理是指“多阶段决策过程的最优决策序列具有这样的性质:不论初始状态和初始决策如何,对于前面决策所造成的某一状态而言,其后各阶段的决策序列必须构成最优策略”。
背包问题的解决过程
每次遍历到的第 i 个物品,根据 w[i]和 v[i]来确定是否需要将该物品 放入背包中。即对于给定的 n 个物品,设 v[i]、w[i]分别为第 i 个物品的价值和重量,C 为背包的容量。再令 v[i][j] 表示在前 i 个物品中能够装入容量为 j 的背包中的最大价值。则我们有下面的结果:
1 2 3 4 5 6 7 8 9
| (1) v[i][0]=v[0][j]=0; (2) 当 w[i]> j 时:v[i][j]=v[i-1][j] 单元格的装入策略 (3) 当 j>=w[i]时: v[i][j]=max{v[i-1][j], v[i]+v[i-1][j-w[i]]}
v[i-1][j]: 就是上一个单元格的装入的最大值 v[i] : 表示当前商品的价值 v[i-1][j-w[i]] : 装入 i-1 商品,到剩余空间 j-w[i]的最大值
|

这样我们就完成了填表找到了商品的最优解,但是最优解由哪些商品构成,我们却不知道,所以我们还有定义一个 item
一维数组,根据回溯法求解出最优解商品构成,在 item
上将其下标标记为1。有如下寻解方式:
- V(i,j)=V(i-1,j)时,说明没有选择第i 个商品,则回到V(i-1,j);
- V(i,j)=V(i-1,j-w(i))+v(i)时,说明装了第i个商品,该商品是最优解组成的一部分,随后我们得回到装该商品之前,即回到V(i-1,j-w(i));
- 一直遍历到i=0结束为止,所有解的组成都会找到。
以上所有代码如下:
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 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76
| public class KnapsackProblem { public static final String things[] = {"", "吉他(G)","音响(S)","电脑(L)"}; public static final int weight[] = {0,1, 4, 3}; public static final int price[] = {0,1500, 3000, 2000};
static int row = things.length; static int column = 4 + 1; static int[][] V = new int[row][column]; static int[] w = weight; static int[] v = price; static int[] item = new int[row];
public static void main(String[] args) {
findMax(); list(); findWhat(row-1,column-1); printWhat(); }
public static void findMax(){ for (int i = 1; i < row; i++) { for (int j = 1; j < column; j++) { if(w[i]>j){ V[i][j] = V[i-1][j]; }else { V[i][j] = Math.max(V[i-1][j],v[i]+V[i-1][j-w[i]]); } } } } public static void list(){ for (int i = 0; i < row; i++) { for (int j = 0; j < column; j++) { System.out.printf("%d\t",V[i][j]); } System.out.println(); } } public static void findWhat(int i, int j){ if(i==0) return; if(V[i][j] == V[i-1][j]){ findWhat(i-1,j); }else if(j-w[i]>=0 && V[i][j] == v[i]+V[i-1][j-w[i]]){ item[i] = 1; findWhat(i-1,j-w[i]); } } public static void printWhat(){ System.out.print("最优解的商品构成:"); for (int i = 1, len = item.length; i < len; i++) { if(item[i] == 1){ System.out.print(things[i]+" "); } } System.out.println(); } }
|
运行结果:
