java - java中动态编程的最小成本

问题描述

我正在做一个项目，我必须通过动态编程找到最小成本。我们A[n*m]填充了一个数组。我们还有另一个数组b[n*m]。我们必须填充另一个c(n*m)数组，其中c(i,j)填充了最小值

for (i=1 to m) 
  a[i,j]+B[j,k]+c[i-1,k]

例如我们有这个数组。

这是我的代码：

for (int t = 1; t < n; t++) {
 for (int y = 0; y < m; y++) {
  int min = 9999555;
  for (int k = 0; k < m; k++) {
   if ((a[t][y] + b[y][k]) < min) {
    min= a[t][y] + b[y][k] + c[t - 1][k];
    }
   }c[t][y] += min;
  }
 }
 for (int u = 0; u < n; u++) {
        for (int z = 0; z < m; z++) {
            System.out.print(c[u][z]+" ");
        }
        System.out.println();
    }

的第一列c应与的第一列相同a。例如： c[2,1]我min{A[2,1]+c[1,1]+b[1,1], A[2,1]+C[1,2]+B[2,1],A[2,1]+c[1,3]+b[3,1]} 想问你我的代码是否是正确的动态规划方法。

标签： javadynamic

让我们明确说明：
A[i,j] 是在 VM j 上运行进程 i 的成本

状态 C[i,j] 意味着在虚拟机“0..j”上运行进程“0..i”的最小成本

现在让我们假设没有 B 成本数组。

目标是状态 C[n,m]，它是在虚拟机“0..m”上运行进程“0..n”的最小成本。
我们可以从以下位置到达状态 C[i,j]：

状态 C[i-1,j] 这意味着虚拟机“0..j”将运行额外的进程“i”并考虑在虚拟机“0..j”上运行进程“i”的成本，即总和（a [i,k]) 其中 k=0..j
因此成本为 C[i-1, j] + sum(a[i,k]) 其中 k=0..j
状态 C[i, j-1] 这意味着进程“0..j”将在另外一个虚拟机“j”上运行（因此总计“0..j”）并考虑到运行进程“0”的成本..i" 在 VM "j" 上是 sum(a[k,j]) 其中 k=0..i
因此成本是 C[i, j-1] + sum(a[k,j]) 其中 k =0..i

通过取这两个值的最小值，我们发现 C[i,j]

到目前为止你同意吗？

更新。
假设进程和 VM 编号从 0 开始：

基本情况：

for(int j=0; j < m; j++)  
     c[ 0 ][ j ] = a[ 0 ][ j ];

DP循环：

for (int i = 1; i < n; i++) 
{
 for (int j = 0; j < m; j++) 
 {
     int min = Integer.MAX_INT;
     for (int k = 0; k < m; k++) 
      {
        if ((a[ i ][ j ] + b[ k ][ j ] + c[ i-1 ][ k ]) < min) 

             min= a[ i ][ j ] + b[ k ][ j ] + c[ i-1 ][ k ];

      }//try every VM

     c[ i ][ j ] = min;

  }//for every VM
}//for every process

java - java中动态编程的最小成本

问题描述

解决方案

推荐阅读