算法学习——动态规划之装载问题

算法描述两艘船各自可装载重量为c1,c2,n个集装箱,各自的重量为w[n],设计一个可以装载的方案,使得两艘船装下全部集装箱算法思路将第一艘船尽量装满(第一艘船放的集装箱的重量之和接近c1),剩余的集装箱放入第二艘船,若剩余的集装箱重量之和大于第二艘船,则无解定义一个一维数组,a[n]存放对应的集装箱的重量定义一个数组,m[i][j]表示第一艘船还可装载的重量j,可取集装箱编号范围为i,i 1.....

算法学习——动态规划之装载问题

算法描述

两艘船各自可装载重量为c1,c2,n个集装箱,各自的重量为w[n],设计一个可以装载的方案,使得两艘船装下全部集装箱

算法思路

  1. 将第一艘船尽量装满(第一艘船放的集装箱的重量之和接近c1),剩余的集装箱放入第二艘船,若剩余的集装箱重量之和大于第二艘船,则无解

  2. 定义一个一维数组,a[n] 存放对应的集装箱的重量

  3. 定义一个数组,m[i][j]表示第一艘船还可装载的重量j,可取集装箱编号范围为i,i 1...n的最大装载重量值

    例如 现在有3个集装箱 重量分别为9,5,3,即a[1]=9 a[2]=5 a[3]=3

    m[1][2]=0 可装载重量为2,此时上述的三个集装箱都不能装入,所以为最大可装载重量为0

    m[1][3]=m[1][4]=3 可装载重量为3或者是4的时候,都是只能装入重量为3的那个集装箱,所以最大可装载重量为3 `

    实际上,这里的3=a[3] m[1][2],是一个递推的关系,具体看下面`

  4. m[i][j]分下面两种情况
    • 0<=j<a[n] (当可装载重量j小于第n个集装箱的重量w[n],此时就不能往船上装此集装箱) m[i][j] = m[i 1][j]

    • j>=a[n]可装载重量j大于或等于第n个集装箱的重量w[n]),此时剩余的可装载重量为j-a[n](装入了此时的集装箱),最大的可装载重量为m[i 1][j-w[n]] w[n]

      但是我们是需要最大的可装载重量,所以得与如果不将当前集装箱装入的那种情况m[i 1][j]进行比较

      m[i][j]=Math.max(m[i 1][j],m[i 1][j-a[n] a[n]])

  5. 上面我们就获得了一个关于m[i][j]的递推关系,我们通过逆推获得全部的数值

    • 初始值

      m[i][j]=0 这里的i=n j从0到a[n] 这里的a[n]是第n个集装箱重量(最后一个集装箱的重量)

      这里的赋值其实就是上述m[i][j]两种情况的第一种情况,最后一个集装箱的重量大于可装载重量,不装载此集装箱,所以最大可装载重量为0,

      m[i][j]=a[n] 这里的i=n j从a[n]到c1 这里的a[n]是第n个集装箱的重量(最后一个集装箱的重量)

      这里的意思为当可装载重量j只要都是大于最后一个集装箱的重量a[n],即可装入此集装箱,所以最大可装载重量等于装入的集装箱的重量

    • 开始逆推

      使用上述的递推公式进行逆推

        for (int i = n; i >= 1 ; i--) {for (int j = 1; j <=c1; j  ) { if(j>=a[i]){  m[i][j] = Math.max(m[i 1][j],m[i 1][j-a[i]] a[i]); }else{  m[i][j]=m[i 1][j]; }}  }
  6. 之后再进行输出,输出第一艘船的装载方案,输出第二艘船的装载方案

算法实现

 System.out.println(“输入第一艘船可装载重量c1:“); Scanner scanner = new Scanner(System.in); int c1 = scanner.nextInt(); System.out.println(“输入第二艘船可装载重量c2:“); int c2 = scanner.nextInt(); System.out.println(“输入集装箱个数n:“); int n = scanner.nextInt(); int[] a = new int[n 1]; //使用一维数组存放集装箱重量 System.out.println(“依次输入集装箱的重量“); for (int i =1; i < n 1; i  ) {  a[i] = scanner.nextInt(); } int sum = 0;//集装箱重量总和 for (int i = 0; i < a.length; i  ) {  sum=sum a[i]; } //超重情况 if(sum>c1 c2){  System.out.println(“集装箱重量之和大于两艘船可装载重量,题目无解“);  return;//结束程序 } int[][] m = new int[100][100];//m[i][j]表示第一艘船还可装载的重量j,可取集装箱编号范围为i,i 1...n的最大装载重量值 //赋初始值,由于是逆推,所以从末尾开始 //可装载重量j小于第n个集装箱重量a[n],不装此集装箱,赋值为0 for (int j = 0; j < a[n]; j  ) {  m[n][j] = 0; } //可装载重量j大于或等于第n个集装箱重量a[n],装载此集装箱,此时刻最大装载重量值为a[n] for (int j = a[n]; j <=c1 ; j  ) {  m[n][j]=a[n]; } //关键逆推代码 for (int i = n; i >= 1 ; i--) {  for (int j = 1; j <=c1; j  ) {if(j>=a[i]){ m[i][j] = Math.max(m[i 1][j],m[i 1][j-a[i]] a[i]);}else{ m[i][j]=m[i 1][j];}  } } int maxc1 = m[1][c1];//最大可装载重量 System.out.println(“maxc1=“ maxc1); if(maxc1>sum-c2){  int cw = m[1][maxc1];  int sw,i;  //输出第一艘船的装载  System.out.println(“第一艘船装载:“);  for (sw=0,i=1;i<=n;i  ){if(m[i][cw]>m[i 1][cw]){ cw = cw-a[i]; sw=sw a[i];//统计sw,sw的最终结果与maxc1相等 System.out.print(a[i] “  “); a[i]=0;//装载当前的集装箱}  }  System.out.print(“(“ sw “)“);  System.out.println(““);  //输出第二艘船的装载  System.out.println(“第二艘船装载:“);  for(sw=0,i=1;i<=n;i  ){//已装载在第一艘船的集装箱a[i]都已经为0了,只需要将不为0的那些集装箱装入第二艘船即可if(a[i]!=0){ System.out.print(a[i] “  “); sw=a[i] sw;}  }  System.out.println(“(“ sw “)“); }else{  System.out.println(“无解“); }

结果

源文地址:https://www.guoxiongfei.cn/cntech/3833.html