java - 无法正确计算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");
         }
      }  

对于下面的输入(<--是我的解释，不包含在输入文本中)

4     <--that's my n
3     <--that's my m

5 6 3
7 8 5    <--that's the *Cost* array
7 8 3
2 7 6

0 7 2
7 0 2    <--that's the *VMs* array
2 2 0 

我应该得到这样的东西

5 6 3 
12 13 8     <-- *NewCost* array
17 18 11
15 20 17

但我明白了

5 6 3 
12 13 8
14 15 8
7 12 9

计算示例:

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];