Минимальная стоимость с динамическим программированием в Java - PullRequest
Новая
       35

Минимальная стоимость с динамическим программированием в Java

0 голосов
/ 26 мая 2018

Я работаю над проектом, где я должен найти минимальную стоимость с динамическим программированием.У нас заполнен массив 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]} Я хочу спросить вас, является ли мой код правильным методом динамического программирования.

Ответы [ 2 ]

0 голосов
/ 26 мая 2018

Посещение облака Работа с динамическими программистами Компании, такие как i Amazon, предоставляют вычислительные облачные вычисления, они все о виртуальном человеке (виртуальные машины, виртуальные машины), которые, в свою очередь, дают их другим. Соответствующее вознаграждение за общее время использования.,В процессе есть много эскизов, каждый из которых отличается, например, одна виртуальная машина A может превосходить стоимость B другой виртуальной машины, чтобы выполнить процесс, использующий больше ЦП, в то время как B превосходит A в выполняющихся процессах.доктор наукМожет также существовать более дорогая система C, которая превосходит как A, так и B по производительности (но это более дорого).Прогнозирование дизайна виртуальной машины - это множество финансовых ресурсов.Эта проблема адресована конкретной работе.У нас есть углубленный процесс, состоящий из N экспериментов в виде цепочек: Δ1 → Δ2 → Δ3 → ..... → ΔΝ.Результаты показывают, что результаты Δ1 передаются в качестве входных данных для Δ2, а для Δ2 - Δ3 и так далее.У нас также есть M виртуальных изобразительных средств.В качестве записи у нас также есть 2 таблицы.Человек - NXM, и он приводит к общей стоимости выполнения транзакции в виртуальной машине одного типа.Таблица сановников является MXM, и она оплачивает стоимость отправки данных другому.Пример ввода следующий: в конкретном примере встроенный процесс имеет 4 сценария и доступны 3 шаблона VM.Первый выполняет 4 подпрограммы со стоимостью 5, 7, 7 и 2 соответственно.Он также связывается с двумя другими типами техников со стоимостью 7 и 2. Алгоритм динамического программирования, который должен быть реализован: Алгоритм заполнения таблицы Таблица NXM, где каждая ячейка затрат (i, j) показывает самую низкую общую стоимостьпроцесс, пока я не живу, когда я живу на JJ.Для того, чтобы начать жизнь в движении, необходимо, чтобы результаты i-1 были либо переданы другим сообществам, либо с учетом затрат на связь.В приведенном выше примере эта таблица имеет эквивалентность, что на практике означает, что менее дорогостоящее вымирание равно 15 и достигается, когда последняя операция представляет собой виртуальную машину:

0 голосов
/ 26 мая 2018

Давайте четко сформулируем:
A [i, j] - это стоимость запуска процесса i на ВМ j

Состояние C [i, j] подразумевает минимальную стоимость запуска процессов "0..i "на виртуальных машинах" 0..j "

Давайте пока предположим, что нет массива затрат B.

Целью является состояние C [n, m], которое представляет собой минимальную стоимость запуска процессов "0..n" на виртуальных машинах "0..m".
Мы можем достичь состояния C [i,j] с:

  1. состояние C [i-1, j], что означает, что виртуальные машины "0..j" будут запускать дополнительный процесс "i" и с учетом затрат на запускобработать "i" на виртуальных машинах "0..j", это сумма (a [i, k]), где k = 0..j
    Следовательно, стоимость равна C [i-1, j] + sum (a [i, k]) где k = 0..j

  2. состояние C [i, j-1], что означает, что процессы "0..j" будут выполняться еще на одной виртуальной машине "j "(итого всего" 0..j ") и с учетом затрат на запуск процессов" 0..i "на ВМ" j "это сумма (a [k, j]), где k = 0..i
    Следовательно, стоимость составляет C [i, j-1] + сумма (a [k, j]), где k = 0..i

Принимая минимум этих двух значениймы находим C [i, j]

Согласны ли вы до сих пор?

ОБНОВЛЕНИЕ.
Предполагается, что нумерация процессов и ВМ начинается с 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
...