Нахождение самой низкой суммы в двумерном массиве, выбирая 1 элемент из каждой строки

Question

Я пишу код, в котором задан матричный массив 2d, и, выбрав по 1 элементу в каждой строке, вы должны вывести наименьшие суммы. Суммы, как в вы должны дать n количество минимальных сумм

#include<iostream>
#include<math.h>
using namespace std; 
int main() { 
    int n;
    cin>>n;
    int hist[n][n];
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin>>hist[i][j];
        }
    }
    int num=pow(n,n);
    int sum[num];
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            sum[i]=sum[i]+hist[i][j];
        }
    }
    for(int i=0;i<n;i++){
        cout<<sum[i]<<" ";
    }

    return 0; 
}

пример ввода будет:

3
1 8 5
9 2 5
10 7 6

Выход будет

9 10 12

с 1+ 2 + 6 = 9; 1 + 2 + 7 = 10; 1 + 2 + 10 Основная проблема, с которой я сталкиваюсь, заключается в том, что я не могу найти самую низкую сумму или даже те суммы, которые я пытался обмануть, но она не сработает. Не могли бы вы помочь мне исправить код, чтобы я мог хотя бы найти суммы?

Answer 1

Много проблем с вашим кодом (это даже не C ++). Но проблема, которая вызывает ваш текущий вопрос, заключается в том, что вы должны инициализировать sum в ноль. на данный момент у вас есть значения мусора в сумме.

int sum[num] = {0};

Некоторые другие проблемы

int num=pow(n,n);

Это вычисляет n в степени n, но есть только n квадратные суммы. Так что это было бы лучше

int sum[n*n] = {0};

Но большая проблема, которая делает ваш код недопустимым в C ++, состоит в том, что в измерениях массива C ++ должны быть постоянные времени компиляции , а не переменные. Так что это

int hist[n][n];

и это

int sum[num];

не являются законными C ++. Они допустимы в C, поэтому ваш компилятор принимает их, но не каждый компилятор C ++ будет. Поскольку вы пытаетесь написать код на C ++, вы должны использовать vector. Вот ваш код, переписанный для использования векторов.

#include <vector>
using std::vector;

...

vector<vector<int>> hist(n, vector<int>(n));

...

vector<int> sum(num, 0);

...

Вот и все, что не нужно менять.

Answer 2

Вместо грубого форсирования почему бы не понять, что наименьший путь - это просто наименьший элемент каждой строки, а второй наименьший путь - наименьший элемент из первых n-1 строк и второй наименьший элемент из n.

Вы можете элегантно express сделать это, сначала отсортировав строки матрицы, а затем сохранив счетчик того, где вы находитесь в каждой строке:

#include <algorithm>
#include <iostream>
#include <vector>

struct path {
  path(int n) : n(n), indexes(n) {}

  // Add one to last row index, then carry over to previous rows.
  path& operator ++() {
    indexes.back()++;
    for (int i = n-1; i >= 0; i--) {
      if (indexes[i] == n) {
        indexes[i] = 0;
        indexes[i-1]++;
      } else {
        break;
      }
    }
    return this;
  }

  int n;
  std::vector<int> indexes;
};

Теперь ваша проблема проста:

int main() { 
    int n;
    cin>>n;
    std::vector<std::vector<int>> hist(n, std::vector<int>(n));

    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin>>hist[i][j];
        }
        // sort each row after reading
        std::sort(hist[i].begin(), hist[i].end());
    }

    int num_minimum_sums = n;
    path p(n);
    while (num_minimum_sums-- > 0) {
      int sum = 0;
      for (int i = 0; i < n; i++) {
        sum += hist[i][p.indexes[i]];
      }
      std::cout << sum << std::endl;
      ++p;
    }
}