20130721【Java】バックトラックトラック法で数値分割問題を解く

お題

10個の数列を３つの仕切りで分割し、グループの中の整数の和の最大値を最小にする分割を求める。

ソース

import java.text.DecimalFormat;

public class List11_3 {
 private static final int array =
  {15, 3, 7, 6, 10, 4, 13, 2, 3, 6};
 private static final int separator = 3;
 
 static class Cell {
  public int sol;
  public int num;
 }
 
 public static void main(String args) {
  Cell solutions = new Cell[array.length][separator + 1];
  
  // 表の後ろから順に埋めていく
  for(int i = array.length - 1; i >= 0; i--) {
   for(int j = 0; j < separator + 1; j++){
    solutions[i][j] = new Cell();
    solutions[i][j].num = 0;
    solutions[i][j].sol = 0;
    int sum = 0;
    for(int s = i; s < array.length; s++){
     sum += array[s];
     if(j == 0 || i == array.length -1 ||
       solutions[i][j].num == 0 ||
       (s != array.length - 1 &&
         solutions[i][j].sol > Math.max(sum,  solutions[s+1][j-1].sol))){
      if(j == 0 || i == array.length - 1){
       // 1行目か最終列ならば、処理なし
       solutions[i][j].sol = sum;
      } else {
       // より良い解決方法を記録する
       solutions[i][j].sol = Math.max(sum,  solutions[s + 1][j - 1].sol);
      }
      solutions[i][j].num = s - i + 1;
     }
    }
   }
  }
  
  // デバッグ用にテーブルを表示
  DecimalFormat format = new DecimalFormat("00");
  for(int j = 0; j < separator + 1; j++) {
   for(int i = 0; i < array.length; i++){
    System.out.print(
      format.format(solutions[i][j].num) + "," +
      format.format(solutions[i][j].sol) + " ");
   }
   System.out.println();
  }
  
  System.out.print("\n最大の和:" +
    solutions[0][separator].sol + "\n分割方法：");
  for(int i=0,j=separator; j >= 0 && i != array.length; --j){
   System.out.print("[" + solutions[i][j].num + "個]");
   i += solutions[i][j].num;
  }
 }
}

実行結果

10,69 09,54 08,51 07,44 06,38 05,28 04,24 03,11 02,09 01,06
04,38 04,28 04,27 03,24 02,24 02,17 01,13 02,06 01,06 01,06
03,25 02,24 03,23 02,17 02,14 01,13 01,13 01,06 01,06 01,06
02,23 03,16 02,14 01,14 01,13 01,13 01,13 01,06 01,06 01,06

最大の和:23
分割方法：[2個][3個][2個][3個]