#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]
Просто догадываюсь, трудно понять ваши намерения, но похоже на алгоритм поиска пути. Ваш код неправильно добавлял стоимость к диагональному или горизонтальному перемещению, и поскольку стоимость начала была равна единице, это также был ваш результат. Это должно вернуть стоимость одиннадцати для вашего образца.