动态规划算法（3）--0-1背包、石子合并、数字三角形

目录

一、0-1背包

1、概述

2、暴力枚举法

3、动态规划

二、石子合并问题

1、概述

2、动态规划

3、环形石子怎么办？

三、数字三角形问题

1、概述

2、递归

3、线性规划

 四、租用游艇问题 

---

一、0-1背包

1、概述

        0-1背包：给定多种物品和一个固定重量W的背包，每种物品有一个固定的重量，价值，现在要将物品装入背包，每种物品至多装入一个，使总重量不超过W，且总价值最大。

        约束条件和优化目标如下：

2、暴力枚举法

        暴力枚举法也是使用递归的方式，假设对前i个物品分析，总重量为c，当前总价值为P。那么存在递归条件：

        另外当重量小于0时，总价值为-∞（代码中可以用-999替代），物品个数小于等于0，总价值为0。

        暴力枚举法依赖递归方式，没有减少子问题个数，所以根据递归树计算，复杂度为。

        伪代码如下：

        代码实例： 

   //暴力枚举public static int violate_knapsack(int weight,int i,int weights[],int values[]){if (weight<0){return -9999; }if (i<=0)  {    return 0;}int p1=violate_knapsack(weight-weights[i],i-1,weights,values);   //选中i物品int p2=violate_knapsack(weight,i-1,weights,values);              //不选i物品int p=p1+values[i]>p2?p1+values[i]:p2;   return p;}

3、动态规划

        动态规划方法通过建立备忘录的方式，前i个物品，总重量为j的时刻永远依赖于前面的子结构。M数组为加入前i个物品后，总重量为j时的总价值，Rec数组表示是否有物品添加，若添加则为1，不添加则为0。

        原理：

参数：count代表总类别个数，weight代表背包重量，weights为物品重量，values为物品价值，name为物品名称。

（1）首先，M数组0行0列均为初值0，注意：行为重量，列为种类个数。

（2）按每行逐个值来填写M和Rec。如：前i个物品，总重量为j的情况下，即求M[i][j]时，如果该物品重量小于背包重量且在前i-1个物品，总重量为（j-当前物品重量）时的总重量+当前物品价值的总价值，大于前i-1个物品，总重量为j时的总价值时M填写较大的总价值，Rec=1。条件写为：

（3）由于调用j-当前物品重量时有可能为负数，所以保证最小值为0，设为minor。

（4）如果不满足（2）条件，则M[i][j]填上一行同列的M[i-1][j]值，即不选这个物品（索引为i-1）的总价值。Rec为0。

（5）最优解追寻：Rec数组倒序查找i取最大值，逐次减1，判断条件如果Rec数组为1，则从总重量weight中减少weights[i-1]，输出name[i-1]物品，直到i取1。

//0-1背包问题
import java.util.ArrayList;
public class backage {public static void main(String []args){int values[]={24,2,9,10,9};int weights[]={10,3,4,5,4};int count=5;int weight=13;int M[][]=new int [count+1][weight+1];int Rec[][]=new int [count+1][weight+1];String name[]={"beer","cocacola","cookie","bread","milk"};//暴力求解System.out.println(violate_knapsack(weight,count-1,weights,values));  //建立M数组，Rec数组 knapsack(count,weight,M,Rec,weights,values);//M数组for(int i=0;i<count+1;i++){for(int j=0;j<weight+1;j++){System.out.print(M[i][j]+"\t");}System.out.println("");}//Rec数组for(int i=0;i<count+1;i++){for(int j=0;j<weight+1;j++){System.out.print(Rec[i][j]+"\t");}System.out.println("");}//输出最优解Print(count,weight,Rec,name,weights);} //动态规划public static void knapsack(int count,int weight,int M[][],int Rec[][],int weights[],int values[]){for(int i=0;i<count+1;i++)         //0行0列没有值参与M[i][0]=0;for(int j=0;j<weight+1;j++)M[0][j]=0;for(int i=1;i<count+1;i++)         //第一行的表示加入第一个物品，但是第一个物品在索引0处{for(int j=1;j<weight+1;j++){int minor;                 //minor的设计是防止j-weights出现小于0，有可能背包重量小于上一行物品的重量，从而小于背包质量，小于背包质量默认为0if(j-weights[i-1]<0)minor=0;elseminor=j-weights[i-1];if((weights[i-1]<=j) & (values[i-1]+M[i-1][minor]>M[i-1][j]))    //如果可以替换,M替换为新值，Rec更新为1{M[i][j]=values[i-1]+M[i-1][minor];Rec[i][j]=1;}else{M[i][j]=M[i-1][j];                                           //不能修改时，M用上一行同列值替换，Rec更新为0Rec[i][j]=0;}}}}//输出最优解public static void Print(int count,int weight,int Rec[][],String name[],int weights[]){for(int i=count;i>0;i--){if(Rec[i][weight]==1){System.out.println(name[i-1]);weight=weight-weights[i-1];}}}

M数组和Rec数组的写法：

二、石子合并问题

1、概述

        现在有n堆石子排成一排，要求将石子有次序地合并成一堆，规定每次只能选相邻的两堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分，设计一个算法将n堆石子合并成一堆的最小得分和最大得分。

        类比矩阵连乘问题求解，利用动态规划，设计m和s数组，最大值为m[1][n]。

2、动态规划

        动态规划转移方程（最小值）：

        

        动态规划转移方程（最大值）：

 

3、环形石子怎么办？

        如果题目要求石子堆围成一圈，其他要求不变，我们可以考虑将数组变为一个重复数组，由环形变为线性。如{1,2,3}则变为{1,2,3,1,2,3}，n=2*n，然后考虑(j-i)>=arr_length时才满足原来的最多三个石子堆合并的问题。

        动态规划转移方程相同，只是多了一个退出循环的条件，同样的生成m数组，假设石子堆为{4,4,5,9}，当前生成最小值m数组应该为下图示例：

        可以看到原先的m[1][n]为最小值，现在应该讨论，也就是四个数的最小值。

        代码示例：

//石子合并问题
public class stonemerge {public static void main(String[] args){int arr[]={4,4,5,9};int n=arr.length;int m[][]=new int[n+1][n+1]; int m_[][]=new int[n*2+1][n*2+1];int s[][]=new int[n+1][n+1]; minserge(arr,m_);System.out.println(trackmin(arr, m_));maxserge(arr, m_);System.out.println(trackmax(arr,m_));}//最小合并m数组 public static void minserge(int arr_[],int m[][]){int n=arr_.length*2;int arr[]=new int[n];add_arr(arr,arr_);for(int i=1;i<n;i++)m[i][i]=0;for (int r = 2; r <=n; r++) {for (int i = 1; i <= n - r + 1; i++) {               int j = i + r - 1;if((j-i)>=arr_.length)break;                m[i][j] = m[i + 1][j] + sum(i,j,arr);				             for (int k = i + 1; k < j; k++){int t = m[i][k] + m[k + 1][j] + sum(i,j,arr);if (t < m[i][j]) m[i][j] = t;}}}}//最大合并m数组public static void maxserge(int arr_[],int m[][]){int n=arr_.length*2;int arr[]=new int[n];add_arr(arr,arr_);for(int i=1;i<n;i++)m[i][i]=0;for (int r = 2; r <=n; r++) {for (int i = 1; i <= n - r + 1; i++) {               int j = i + r - 1;if((j-i)>=arr_.length)break;                m[i][j] = m[i + 1][j] + sum(i,j,arr);				             for (int k = i + 1; k < j; k++){int t = m[i][k] + m[k + 1][j] + sum(i,j,arr);if (t > m[i][j]) m[i][j] = t;}}}}//合并代价public static int sum(int i,int j, int arr[]){int tot=0;for(int m=i-1;m<=j-1;m++)tot+=arr[m];return tot;}//环形转线性数组生成public static void add_arr(int arr[],int arr_[]){for(int i=0;i<arr.length;i++){if(i<arr_.length)arr[i]=arr_[i];elsearr[i]=arr_[i-arr_.length];}}//最小值public static int trackmin(int arr[],int m[][]){int n=arr.length;int min=m[1][n];for(int i=2;i<=n;i++){if(m[i][n+i-1]<min)min=m[i][n+i-1];}return min;}//最大值public static int trackmax(int arr[],int m[][]){int n=arr.length;int max=m[1][n];for(int i=2;i<=n;i++){if(m[i][n+i-1]>max)max=m[i][n+i-1];}return max;}
}

三、数字三角形问题

1、概述

        给定一个由n行数字组成的数字三角形，设计算法，计算从三角形的顶至底的一条路径，每次必须下降一层，使该路径经过数字总和最大，如下图路线7-3-8-7-5，总和30。

2、递归

递归条件：

               当x==n-1时为最底层数字，返回该数字。

//递归方法
public static int test(int x,int y,int nums[][]) {int n=nums.length;if(x == n-1) {return nums[x][y];}return (nums[x][y] + (test(x+1,y,nums) >= test(x+1,y+1,nums) ? test(x+1,y,nums) : test(x+1,y+1,nums)));}

3、线性规划

        状态转移方程与递归条件一样，只不过从倒数第二层向上叠加（参数i），每层的值改变为当前层到底层的最大值，变量k遍历某一层的每个数字，计算到底层的最大值并保存。

//动态规划
public static int max(int nums[][])
{for(int i=nums.length-2;i>=0;i--){int j=nums[i].length;for(int k=0;k<j;k++){nums[i][k]+=(nums[i+1][k]>=nums[i+1][k+1]?nums[i+1][k]:nums[i+1][k+1]);}}return nums[0][0];
}

 四、租用游艇问题

        游艇出租站租用游艇，并在下游的任何一个游艇出租站归还游艇，游艇出租站i到游艇出租站j之间的租金为r（i，j）（1<=i<j<=n）,设计算法，计算出游艇出租站1到游艇出租站n的最少租金。

        输入的数字，第一行代表1到2的距离和1到3的距离，第二行代表2到3的距离。

//租用游艇问题
public class rentyacht {public static void main(String [] args){int cost[][]={{5,15},{7}};int n=cost.length;System.out.println(rentmin(cost,n));} public static int rentmin(int[][] cost, int n) {int[][] best = new int[n + 1][n + 1];for(int i = n - 1; i >= 1; i--) {best[i][n] = cost[i-1][n-1];for(int j = n - 1; j > i; j--) {best[i][n] = cost[i-1][j-1] + best[j][n]<best[i][n]?cost[i-1][j-1] + best[j][n]:best[i][n];}}return best[1][n];}
}