минимальная сумма затрат

#c #algorithm

#c #алгоритм

Вопрос:

я хочу рассчитать минимальную сумму в заданном двумерном массиве

 #include<iostream>
#include<limits.h>
using namespace std;
#define R 3
#define C 3
int Min(int x,int y,int z){
   if(x<y){
        return (x<z)?x:z;
   }
   else
       return (y<z)?y:z;
   }
int mincost(int cost[R][C],int m,int n){

    int i,j;
    int t[R][C];
    t[0][0]=cost[0][0];
    for(i=1;i<=m;i  )
        t[i][0]=t[i-1][0] cost[i][0];
    for(j=1;j<=n;j  )
t[0][j]=t[0][j-1] cost[0][j];
    for(i=1;i<=m;i  ){
        for(j=1;j<=n;j  ){
            t[i][j]=Min(t[i-1][j-1],t[i-1][j],t[i][j-1] cost[i][j]);
        }
    }
      return t[m][n];

}

int main(){

    int cost[R][C]={{1,2,3},
                    {4,8,2},
                    {1,5,3}};
    cout<<mincost(cost,2,2)<<endl;


    return 0;
}
  

от начальной точки (0,0) до некоторой точки (m, n) для этого массива оно равно 8, но вывод показывает мне 1, почему?что не так с этим кодом?
алгоритм в словах

Учитывая матрицу затрат cost[][] и позицию (m, n) в cost[][], напишите функцию, которая возвращает стоимость пути с минимальными затратами для достижения (m, n) из (0, 0). Каждая ячейка матрицы представляет стоимость прохождения через эту ячейку. Общая стоимость пути для достижения (m, n) — это сумма всех затрат на этом пути (включая как исходный, так и конечный). Вы можете перемещаться только вниз, вправо и по диагонали нижних ячеек из данной ячейки, т. Е. Из данной ячейки (i, j) могут быть пройдены ячейки (i 1, j), (i, j 1) и (i 1, j 1). Вы можете предположить, что все затраты являются целыми положительными числами.

Комментарии:

1. Можете ли вы описать свой алгоритм словами? Это было бы уместно для блока комментариев в вашем коде.

2. Я не могу придумать никакого способа интерпретировать это, когда результат равен 8, за исключением нахождения максимального элемента: (

3. Добавленное вами описание было не описанием вашего алгоритма , а скорее описанием постановки задачи .

4. да, но вот подсказка для алгоритма, так в чем проблема с моими определениями проблем? это динамическая реализация кода

Ответ №1:

Я вижу, что это решение для динамического программирования.

здесь у вас опечатка:

 t[i][j]=Min(t[i-1][j-1],t[i-1][j],t[i][j-1] cost[i][j]);
  

это должно быть:

 t[i][j]=Min(t[i-1][j-1],t[i-1][j],t[i][j-1])   cost[i][j];
  

в основном это работало так t[i][j] = t[i-1][j-1] .

Примечание: Хорошим способом отладки этих проблем является печать промежуточной матрицы (здесь : t ).

Ответ №2:

Учитывая, что t[0] [0] = стоимость [0] [0] = 1, тогда

 for(i=1;i<=m;i  ){
        for(j=1;j<=n;j  ){
            t[i][j]=Min(t[i-1][j-1],t[i-1][j],t[i][j-1] cost[i][j]);
        }
  

для i = 1, j =1

 t[1][1] = Min(t[0][0], t[0][1], t[1][0] cost[1][1]) = Min(1, ...) = 1
  

для i = 2 j = 2

 t[2][2] = Min(t[1][1], t[1][2], t[2][1] cost[2][2]) = Min(1, ...) = 1
  

Ответ №3:

 Min(t[i-1][j-1],t[i-1][j],t[i][j-1] cost[i][j])
  

вероятно, должно быть

 Min(t[i-1][j-1],t[i-1][j],t[i][j-1])  cost[i][j]
  

Просто догадываюсь, трудно понять ваши намерения, но похоже на алгоритм поиска пути. Ваш код неправильно добавлял стоимость к диагональному или горизонтальному перемещению, и поскольку стоимость начала была равна единице, это также был ваш результат. Это должно вернуть стоимость одиннадцати для вашего образца.