嗯,我有程序的这一部分,不管我做什么,我都不能得到我期望的输出。我使用了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}
发布于 2018-05-30 07:52:26
我们仍然不能真正理解您试图解决的问题,但从您的示例计算中可以看出,您希望在加法中包含的第一个值是最外层循环的前一次迭代的最佳值。您的问题是,您只将之前的迭代保存在NewCost
中,而只从Cost
中读取值。
对于NewCost[2][0]
,您计算了X3=Cost[1][2]+Cost[2][0]+VMs[2][0] = 8+7+2 = 17
,这是不准确的。因为它来自原始的Cost
数组,所以Cost[1][2]
是5,而不是8。如果您希望从上一次迭代中检索8,则需要从保存该结果的NewCost
数组中查找它。
这就是动态编程的要点,在下一轮计算中使用您最近计算出的最佳值。但是它只有在你使用你最近的计算的时候才有效!
试着改变
y = Cost[i-1][k] + Cost[i][j] + Vms[k][j];
至
y = NewCost[i-1][k] + Cost[i][j] + Vms[k][j];
https://stackoverflow.com/questions/50591922
复制相似问题