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

    目录

    一、0-1背包

    1、概述

    2、暴力枚举法

    3、动态规划

    二、石子合并问题

    1、概述

    2、动态规划

    3、环形石子怎么办？

    三、数字三角形问题

    1、概述

    2、递归

    3、线性规划

     四、租用游艇问题 

    一、0-1背包

    1、概述

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

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

    2、暴力枚举法

            暴力枚举法也是使用递归的方式，假设对前i个物品分析，总重量为c，当前总价值为P。那么存在递归条件：\begin{matrix} \quad \qquad p1=knapsack(i-1,c-w_i)\\ \quad p2=knapsack(i-1,c) \\ P=max(p1+v_i,p2) \end{matrix}

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

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

            伪代码如下：

            代码实例： 

    1.    //暴力枚举
    2.    public static int violate_knapsack(int weight,int i,int weights[],int values[])
    3.    {
    4.         if (weight<0)
    5.         {
    6.             return -9999; 
    7.         }
    8.               
    9.         if (i<=0)  
    10.         {    
    11.             return 0;
    12.         }
    13.         int p1=violate_knapsack(weight-weights[i],i-1,weights,values);   //选中i物品
    14.         int p2=violate_knapsack(weight,i-1,weights,values);              //不选i物品
    15.         int p=p1+values[i]>p2?p1+values[i]:p2;   
    16.         return p;
    17.    }

    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。条件写为：weights[i-1]\leqslant j,values[i-1]+M[i-1][j-weights[i]]>M[i-1][j]

    （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。

    1. //0-1背包问题
    2. import java.util.ArrayList;
    3. public class backage {
    4.    public static void main(String []args)
    5.    {
    6.         int values[]={24,2,9,10,9};
    7.         int weights[]={10,3,4,5,4};
    8.         int count=5;int weight=13;
    9.         int M[][]=new int [count+1][weight+1];
    10.         int Rec[][]=new int [count+1][weight+1];
    11.         String name[]={"beer","cocacola","cookie","bread","milk"};
    12.         //暴力求解
    13.         System.out.println(violate_knapsack(weight,count-1,weights,values));  
    14.         //建立M数组，Rec数组 
    15.         knapsack(count,weight,M,Rec,weights,values);
    16.         //M数组
    17.         for(int i=0;i1;i++)
    18.         {
    19.             for(int j=0;j1;j++)
    20.             {
    21.                 System.out.print(M[i][j]+"\t");
    22.             }
    23.             System.out.println("");
    24.         }
    25.         //Rec数组
    26.         for(int i=0;i1;i++)
    27.         {
    28.             for(int j=0;j1;j++)
    29.             {
    30.                 System.out.print(Rec[i][j]+"\t");
    31.             }
    32.             System.out.println("");
    33.         }
    34.         //输出最优解
    35.         Print(count,weight,Rec,name,weights);
    36.    } 
    37.  
    38.    //动态规划
    39.    public static void knapsack(int count,int weight,int M[][],int Rec[][],int weights[],int values[])
    40.    {
    41.  
    42.         for(int i=0;i1;i++)         //0行0列没有值参与
    43.             M[i][0]=0;
    44.         for(int j=0;j1;j++)
    45.             M[0][j]=0;
    46.         for(int i=1;i1;i++)         //第一行的表示加入第一个物品，但是第一个物品在索引0处
    47.         {
    48.             for(int j=1;j1;j++)
    49.             {
    50.                 int minor;                 //minor的设计是防止j-weights出现小于0，有可能背包重量小于上一行物品的重量，从而小于背包质量，小于背包质量默认为0
    51.                 if(j-weights[i-1]<0)
    52.                     minor=0;
    53.                 else
    54.                     minor=j-weights[i-1];
    55.                 if((weights[i-1]<=j) & (values[i-1]+M[i-1][minor]>M[i-1][j]))    //如果可以替换,M替换为新值，Rec更新为1
    56.                 {
    57.                     M[i][j]=values[i-1]+M[i-1][minor];
    58.                     Rec[i][j]=1;
    59.                 }
    60.                 else{
    61.                     M[i][j]=M[i-1][j];                                           //不能修改时，M用上一行同列值替换，Rec更新为0
    62.                     Rec[i][j]=0;
    63.                 }
    64.             }
    65.         }
    66.    }
    67.  
    68.    //输出最优解
    69.    public static void Print(int count,int weight,int Rec[][],String name[],int weights[])
    70.    {
    71.         for(int i=count;i>0;i--)
    72.         {
    73.             if(Rec[i][weight]==1)
    74.             {
    75.                 System.out.println(name[i-1]);
    76.                 weight=weight-weights[i-1];
    77.             }
    78.         }
    79.    }

    M数组和Rec数组的写法：

    二、石子合并问题

    1、概述

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

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

    2、动态规划

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

            m[i][j]=\begin{Bmatrix} 0 \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \quad i=j\\ min(m[i][k]+m[k+1][j]+sum(i,j)) \quad i<j \end{Bmatrix}

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

     m[i][j]=\begin{Bmatrix} 0 \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \quad i=j\\ max(m[i][k]+m[k+1][j]+sum(i,j)) \quad i<j \end{Bmatrix}

    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]为最小值，现在应该讨论min(m[i][n+i-1]) \quad 1\leqslant i\leqslant n，也就是四个数的最小值。

            代码示例：

    1. //石子合并问题
    2. public class stonemerge {
    3.    public static void main(String[] args)
    4.    {
    5.         
    6.         int arr[]={4,4,5,9};
    7.         int n=arr.length;
    8.         int m[][]=new int[n+1][n+1]; int m_[][]=new int[n*2+1][n*2+1];
    9.         int s[][]=new int[n+1][n+1]; 
    10.         minserge(arr,m_);
    11.         System.out.println(trackmin(arr, m_));
    12.         maxserge(arr, m_);
    13.         System.out.println(trackmax(arr,m_));
    14.    }
    15.    //最小合并m数组 
    16.    public static void minserge(int arr_[],int m[][])
    17.    {
    18.         int n=arr_.length*2;
    19.         int arr[]=new int[n];
    20.         add_arr(arr,arr_);
    21.         for(int i=1;i
    22.             m[i][i]=0;
    23.         for (int r = 2; r <=n; r++) 
    24.         {
    25. 			for (int i = 1; i <= n - r + 1; i++) 
    26.             {               
    27. 				int j = i + r - 1;
    28.                 if((j-i)>=arr_.length)
    29.                     break;                
    30.                 m[i][j] = m[i + 1][j] + sum(i,j,arr);				             
    31. 				for (int k = i + 1; k < j; k++)
    32.                  {
    33. 					int t = m[i][k] + m[k + 1][j] + sum(i,j,arr);
    34. 					if (t < m[i][j]) 
    35. 						m[i][j] = t;
    36. 				}
    37. 			}
    38. 		}
    39.    }
    40.    //最大合并m数组
    41.    public static void maxserge(int arr_[],int m[][])
    42.    {
    43.         int n=arr_.length*2;
    44.         int arr[]=new int[n];
    45.         add_arr(arr,arr_);
    46.         for(int i=1;i
    47.             m[i][i]=0;
    48.         for (int r = 2; r <=n; r++) 
    49.         {
    50. 			for (int i = 1; i <= n - r + 1; i++) 
    51.             {               
    52. 				int j = i + r - 1;
    53.                 if((j-i)>=arr_.length)
    54.                     break;                
    55.                 m[i][j] = m[i + 1][j] + sum(i,j,arr);				             
    56. 				for (int k = i + 1; k < j; k++)
    57.                  {
    58. 					int t = m[i][k] + m[k + 1][j] + sum(i,j,arr);
    59. 					if (t > m[i][j]) 
    60. 						m[i][j] = t;
    61. 				}
    62. 			}
    63. 		}
    64.    }
    65.    //合并代价
    66.    public static int sum(int i,int j, int arr[])
    67.    {
    68.         int tot=0;
    69.         for(int m=i-1;m<=j-1;m++)
    70.             tot+=arr[m];
    71.         return tot;
    72.    }
    73.    //环形转线性数组生成
    74.    public static void add_arr(int arr[],int arr_[])
    75.    {
    76.         for(int i=0;i
    77.         {
    78.             if(i
    79.                 arr[i]=arr_[i];
    80.             else
    81.                 arr[i]=arr_[i-arr_.length];
    82.         }
    83.    }
    84.    //最小值
    85.    public static int trackmin(int arr[],int m[][])
    86.    {
    87.         int n=arr.length;
    88.         int min=m[1][n];
    89.         for(int i=2;i<=n;i++)
    90.         {
    91.             if(m[i][n+i-1]
    92.                 min=m[i][n+i-1];
    93.         }
    94.         return min;
    95.    }
    96.    //最大值
    97.    public static int trackmax(int arr[],int m[][])
    98.    {
    99.         int n=arr.length;
    100.         int max=m[1][n];
    101.         for(int i=2;i<=n;i++)
    102.         {
    103.             if(m[i][n+i-1]>max)
    104.                 max=m[i][n+i-1];
    105.         }
    106.         return max;
    107.    }
    108. }

    三、数字三角形问题

    1、概述

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

    2、递归

    递归条件：

    nums[x][y]+=max(trest(x+1,y),test(x+1,y+1)) \ x\neq n-1

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

    1. //递归方法
    2. public static int test(int x,int y,int nums[][]) {
    3.         int n=nums.length;
    4.         if(x == n-1) {
    5.             return nums[x][y];
    6.         }
    7.         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)));
    8.     }

    3、线性规划

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

    1. //动态规划
    2. public static int max(int nums[][])
    3. {
    4.         for(int i=nums.length-2;i>=0;i--)
    5.         {
    6.             int j=nums[i].length;
    7.             for(int k=0;k
    8.             {
    9.                 nums[i][k]+=(nums[i+1][k]>=nums[i+1][k+1]?nums[i+1][k]:nums[i+1][k+1]);
    10.             }
    11.         }
    12.         return nums[0][0];
    13. }

     四、租用游艇问题

            游艇出租站租用游艇，并在下游的任何一个游艇出租站归还游艇，游艇出租站i到游艇出租站j之间的租金为r（i，j）（1<=i

            输入的数字，第一行代表1到2的距离和1到3的距离，第二行代表2到3的距离。一般输入的二维数组都是起始从1开始，以主对角线分布的，这一点可以参见三角形剖分问题。

            租用游艇问题其实本质上也是一个矩阵相乘的问题，所以可以共用矩阵相乘的函数嵌套部分，记住（i，j）的执行顺序就是dp数组的计算顺序。

            dp数组原理：首先dp数组等于cost数组值，若i和j之间存在一个整数，则定义k，使得dp[i][j]=min(dp[i][k]+dp[k][j],dp[i][j]) \quad 1\leqslant i< k<j\leqslant n

            代码示例：

    1. //租用游艇问题
    2. import java.util.Scanner;
    3. public class rentyacht {
    4.    public static void main(String [] args)
    5.    {
    6.         int n=new Scanner(System.in).nextInt();
    7.         int [][]cost=new int[200][200];
    8.         int [][]dp=new int[200][200];
    9.         for(int i=1;i
    10.         {
    11.             for(int j=i+1;j<=n;j++)
    12.             {
    13.                 cost[i][j]=new Scanner(System.in).nextInt();
    14.             }
    15.         }
    16.         System.out.println(rentmin(cost,dp,n));
    17.    } 
    18.    public static int rentmin(int[][] cost, int [][]dp,int n) {
    19.         for(int r=2;r<=n;r++)
    20.         {
    21.             for(int i=1;i<=n-r+1;i++)
    22.             {
    23.                 int j=i+r-1;
    24.                 dp[i][j]=cost[i][j];
    25.                 for(int k=i+1;k
    26.                 {
    27.                     dp[i][j]=Math.min(cost[i][j],cost[i][k]+cost[k][j]);
    28.                 }
    29.             }
    30.         }
    31.         return dp[1][n];
    32.     }
    33. }
  • 相关阅读:
    Improper integral
    python商城
    15：00面试，15：08就出来了，问的问题有点变态。。。
    Bug | 项目中数据库查询问题
    羽夏看Linux内核——环境搭建
    如何解决研发数据传输层面安全可控、可追溯的共性需求？
    JavaPTA练习题 6-2 数字校验
    机器学习练习——熔池状态识别
    工厂模式进阶用法，如何动态选择对象？
    【RocketMQ】RocketMQ5.0新特性（一）- Proxy
  • 原文地址：https://blog.csdn.net/m0_60177079/article/details/133843317