Не могу правильно рассчитать 2d массив в Java

Question

Ну, у меня есть эта часть программы, и я не могу получить результат, который я ожидаю, независимо от того, что я делаю.Я использовал 8 'println' в отчаянной попытке найти свою ошибку, но все еще не могу понять, что мне делать.Хотя я думаю, что проблема начинается со второго значения k .. k = 1 .

   public static void main(String[] args) throws IOException {

      String path = args[0];
      BufferedReader br = null;
      String line;

       int count = 0;
       while ((line=br.readLine()) != null) {

              if (count==0) {
                 int n = Integer.parseInt(line);
             }

            else if (count==1) {
                 int m = Integer.parseInt(line);
                 int Cost = new int[n][m];
                 int VMs = new int[m][m];
            }

           else if (count>=3 && count<n+3) { 
                   String[] Spliter = line.split("\\s+"); 
                   for (int j = 0; j < m; j++) {
                 String str = Spliter[j];
                 int x = Integer.parseInt(str);
                 Cost[count-3][j] = x;
                   }
           }

           else if (count>=n+4 && count<=n+4+m) {
                   String[] Spliter = line.split("\\s+");
                   for (int k = 0; k < m; k++) {
                       String str = Spliter[k];
                       int x = Integer.parseInt(str);
                       Vms[count-n-4][k] = x; 
                    }
           }

           count++;
         }

           int[][] NewCost = new int[n][m];
                for (int w = 0; w<m; w++){
                    NewCost[0][w]=Cost[0][w];
           }

           for (int i = 1; i<n; i++){
                for (int j = 0; j<m; j++){
                   int a = 10000;

                   for (int k = 0; k<m; k++){
                       y = Cost[i-1][k] + Cost[i][j] + Vms[k][j];

                       if (y < a) {
                          NewCost[i][j] = y;
                          a = y;
                       }
                   }
                }
            }

           for (int i = 0; i<n; i++) {
               for (int j = 0; j<m; j++) {
                 System.out.print(NewCost[i][j] + " ");
               }
                  System.out.print("\n");
         }
      }  

для ввода ниже ( <- </strong> моипояснения и не включены во входной текстрасчеты:

NewCost[0][j] = Cost[0][j]     <-- this must be true in every possible input. 
To be specific, in this example we want the first row NewCost[0][j] = {5 , 6 , 3}

NewCost[1][0] = min(X1,X2,X3) = min(12,20,12) = 12
X1=Cost[0][0]+Cost[1][0]+VMs[0][0] = 5+7+0 = 12
X2=Cost[0][1]+Cost[1][0]+VMs[1][0] = 6+7+7 = 20
X3=Cost[0][2]+Cost[1][0]+VMs[2][0] = 3+7+2 = 12

NewCost[1][1] = min(Y1,Y2,Y3) = min(20,14,13) = 13
Y1=Cost[0][0]+Cost[1][1]+VMs[0][1] = 5+8+7 = 20
Y2=Cost[0][1]+Cost[1][1]+VMs[1][1] = 6+8+0 = 14
Y3=Cost[0][2]+Cost[1][1]+VMs[2][1] = 3+8+2 = 13

NewCost[1][2] = min(Z1,Z2,Z3) = min(12,13,8) = 8
Z1=Cost[0][0]+Cost[1][2]+VMs[0][2] = 5+5+2 = 12
Z2=Cost[0][1]+Cost[1][2]+VMs[1][2] = 6+5+2 = 13
Z3=Cost[0][2]+Cost[1][2]+VMs[2][2] = 3+5+0 = 8

So the second row will be NewCost[1][j] = {12 , 13 , 8}

NewCost[2][0] = min(X1,X2,X3) = min(19,27,17) = 17
X1=Cost[1][0]+Cost[2][0]+VMs[0][0] = 12+7+0 = 19
X2=Cost[1][1]+Cost[2][0]+VMs[1][0] = 13+7+7 = 27
X3=Cost[1][2]+Cost[2][0]+VMs[2][0] = 8+7+2 = 17

NewCost[2][1] = min(Y1,Y2,Y3) = min(27,21,18) = 18
Y1=Cost[1][0]+Cost[2][1]+VMs[0][1] = 12+8+7 = 27
Y2=Cost[1][1]+Cost[2][1]+VMs[1][1] = 13+8+0 = 21
Y3=Cost[1][2]+Cost[2][1]+VMs[2][1] = 8+8+2 = 18

NewCost[2][2] = min(Z1,Z2,Z3) = min(17,18,11) = 11
Z1=Cost[1][0]+Cost[2][2]+VMs[0][2] = 12+3+2 = 17
Z2=Cost[1][1]+Cost[2][2]+VMs[1][2] = 13+3+2 = 18
Z3=Cost[1][2]+Cost[2][2]+VMs[2][2] = 8+3+0 = 11

So the third row will be NewCost[2][j] = {17 , 18 , 11}

NewCost[3][0] = min(X1,X2,X3) = min(19,27,15) = 15
X1=Cost[2][0]+Cost[3][0]+VMs[0][0] = 17+2+0 = 19
X2=Cost[2][1]+Cost[3][0]+VMs[1][0] = 18+2+7 = 27
X3=Cost[2][2]+Cost[3][0]+VMs[2][0] = 11+2+2 = 15

NewCost[3][1] = min(Y1,Y2,Y3) = min(31,25,20) = 20
Y1=Cost[2][0]+Cost[3][1]+VMs[0][1] = 17+7+7 = 31
Y2=Cost[2][1]+Cost[3][1]+VMs[1][1] = 18+7+0 = 25
Y3=Cost[2][2]+Cost[3][1]+VMs[2][1] = 11+7+2 = 20

NewCost[3][2] = min(Z1,Z2,Z3) = min(25,26,17) = 17
Z1=Cost[2][0]+Cost[3][2]+VMs[0][2] = 17+6+2 = 25
Z2=Cost[2][1]+Cost[3][2]+VMs[1][2] = 18+6+2 = 26
Z3=Cost[2][2]+Cost[3][2]+VMs[2][2] = 11+6+0 = 17

So the forth row will be NewCost[3][j] = {15 , 20 , 17}

Answer 1

Мы до сих пор не понимаем проблему, которую вы пытаетесь решить, но из ваших примеров расчетов видно, что первое значение, которое вы хотите включить в свои добавления, - это оптимизированное значение из предыдущей итерации самого внешнего цикла.Ваша проблема в том, что вы сохранили предыдущую итерацию только в NewCost, но читаете только значения из Cost.

Для NewCost[2][0] вы вычислили X3=Cost[1][2]+Cost[2][0]+VMs[2][0] = 8+7+2 = 17, что является неточным.Cost[1][2] равно 5, а не 8, как это происходит из исходного массива Cost.Если вы хотите получить 8 из предыдущей итерации, вам нужно найти его в массиве NewCost, в котором вы сохранили этот результат.

Это точка динамического программирования,использовать оптимальные значения, которые вы недавно рассчитали в следующем раунде расчетов.Но это работает, только если вы используете свои последние расчеты!

Попробуйте изменить

y = Cost[i-1][k] + Cost[i][j] + Vms[k][j];

на

y = NewCost[i-1][k] + Cost[i][j] + Vms[k][j];