Как найти минимальную сумму в матрице - Исправление недочетов и поиск решений вместе с Examum.ru

0 / 0 / 0

Регистрация: 21.01.2015

Сообщений: 34

Найти минимальную сумму по строкам матрицы

21.01.2015, 15:36. Показов 3817. Ответов 10

а) минимальную сумму по строкам;
б) сумму минимальных элементов в каждой строке;

all_angarsk

761 / 268 / 57

Регистрация: 13.12.2009

Сообщений: 1,073

21.01.2015, 16:33

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
 
namespace ConsoleМатриц
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("Создание матрицы ");
            Console.WriteLine("Введите число строк матрицы ");
            int n = Convert.ToInt32(Console.ReadLine());
            Console.WriteLine("Введите число столбцов матрицы ");
            int m = Convert.ToInt32(Console.ReadLine());
            int[] sum = new int[n]; string t = ""; int SumMin = 0;
            Random r = new Random();
            int[] min = new int[n];
            int[,] M = new int[n,m];
            for (int i = 0; i < n; i++)
            {
                min[i] = 100;
                for (int j = 0; j < m; j++)
                {
                    
                    M[i, j] = r.Next(-25,50);
                    min[i] = Math.Min(min[i], M[i,j]);
                    sum[i] = sum[i] + M[i, j];
                    t = t + "t" + Convert.ToString(M[i, j]);
                }
                Console.WriteLine(t); t = "";
            }
            Console.WriteLine();
            int Min = 100;
            Console.WriteLine("Суммы строк матрицы и минимальный элемент");
            for (int i = 0; i < n; i++)
            {
                Console.WriteLine(sum[i] + "t" + min[i]);
                Min = Math.Min(Min,sum[i]);
                SumMin = SumMin + min[i];
            }
            Console.WriteLine();
            Console.WriteLine("Минимальная сумма строки матрицы ");
            Console.WriteLine(Min);
            Console.WriteLine("Сумма минимальных элементов из каждой строки ");
            Console.WriteLine(SumMin);
            Console.ReadLine();
        }
    }
}

Prog_maker

455 / 400 / 152

Регистрация: 23.01.2011

Сообщений: 1,054

21.01.2015, 16:52

        static void Main(string[] args)
        {
            Console.WriteLine("Введите количество строк:");
            int n = int.Parse(Console.ReadLine());
            Console.WriteLine("Введите количество столбцов:");
            int m = int.Parse(Console.ReadLine());
            Random rnd = new Random();
            int[,] matrix = new int [n, m];
            List<int> temp = new List<int>();
            List<int> minsum = new List<int>();
 
            for (int i = 0; i < n; i++)
            {
                temp.Clear();
                for (int j = 0; j < m; j++)
                {
                    temp.Add(matrix[i, j] = rnd.Next(36, 42));
                    Console.Write("{0}t",matrix[i,j] );
                }
                minsum.Add(temp.Sum());
                Console.WriteLine();
            }
            Console.WriteLine("nМинимальная сумма по строкам {0}", minsum.Min());
            Console.Write("Сумма минимальных элементов в каждой строке {0}", minsum.Sum());
            
            Console.ReadKey();
        
        }

761 / 268 / 57

Регистрация: 13.12.2009

Сообщений: 1,073

22.01.2015, 04:43

Сообщение от Prog_maker

Console.WriteLine(«nМинимальная сумма по строкам {0}», minsum.Min());
* * * * * * Console.Write(«Сумма минимальных элементов в каждой строке {0}», minsum.Sum());

Не получается сумма минимальных элементов по строкам?

Миниатюры

Prog_maker

455 / 400 / 152

Регистрация: 23.01.2011

Сообщений: 1,054

22.01.2015, 06:07

       static void Main(string[] args)
        {
            Console.WriteLine("Введите количество строк:");
            int n = int.Parse(Console.ReadLine());
            Console.WriteLine("Введите количество столбцов:");
            int m = int.Parse(Console.ReadLine());
            Random rnd = new Random();
            int[,] matrix = new int [n, m];
            List<int> temp = new List<int>();
            List<int> minsum = new List<int>();
            List<int> minele = new List<int>();
 
            for (int i = 0; i < n; i++)
            {
                temp.Clear();
                for (int j = 0; j < m; j++)
                {
                    temp.Add(matrix[i, j] = rnd.Next(36, 42));
                    Console.Write("{0}t",matrix[i,j] );
                }
                minsum.Add(temp.Sum());
                minele.Add(temp.Min());
 
                Console.WriteLine();
            }
            Console.WriteLine("nМинимальная сумма по строкам {0}", minsum.Min());
            Console.Write("Сумма минимальных элементов в каждой строке {0}", minele.Sum());
            Console.ReadKey();
        }

Добавлено через 54 секунды
all_angarsk, Дошло в чем ошибочка, вчера этих задач целая куча была, вот исправил

ture

553 / 361 / 206

Регистрация: 27.11.2014

Сообщений: 1,043

22.01.2015, 19:29

int[,] M = new int[,] {{1,2,3,7},{1,2,3,5},{1,2,3,6}};
            var q=from i in Enumerable.Range(0, M.GetLength(0))
                  join j in Enumerable.Range(0, M.GetLength(1)) on 1 equals 1
                  let v=new { i=i, val=M[i, j] }
                  group v by v.i into g
                  let w=new { sum=g.Sum(x => x.val)}
                  orderby w.sum
                  select w.sum;
            Console.WriteLine(q.ToArray()[0]);

455 / 400 / 152

Регистрация: 23.01.2011

Сообщений: 1,054

23.01.2015, 11:04

ture, Я думаю такой код студенты вряд ли поймут

1981 / 1205 / 440

Регистрация: 13.06.2013

Сообщений: 4,095

23.01.2015, 11:07

Сообщение от Prog_maker

Я думаю такой код студенты вряд ли поймут

Такие студенты в любом случае ничего не поймут. Да и пытаться не будут, пока совсем не припечет.

455 / 400 / 152

Регистрация: 23.01.2011

Сообщений: 1,054

23.01.2015, 11:19

Сообщение от tarasalk

Такие студенты в любом случае ничего не поймут. Да и пытаться не будут, пока совсем не припечет.

В точку сказано

ture

553 / 361 / 206

Регистрация: 27.11.2014

Сообщений: 1,043

23.01.2015, 11:41

Вторая для продвинутых студентов.

int q=(from i in Enumerable.Range(0, M.GetLength(0))
                   join j in Enumerable.Range(0, M.GetLength(1)) on 1 equals 1
                   let v=new { i=i, val=M[i, j] }
                   group v by v.i into g
                   select g.Min(x => x.val)).Sum();
                  
            Console.WriteLine(q);

455 / 400 / 152

Регистрация: 23.01.2011

Сообщений: 1,054

23.01.2015, 14:11

Сообщение от ture

Enumerable.Range

Разве матрица?

Источник

this is another algorithms problem related to dynamic programming

Here is the problem :

find the minimum sum of the given matrix such that select one in each row and column

For example :

3 4 2

8 9 1

7 9 5

the minimum one : 4 + 1 + 7

I think the solution is network flow (max flow/min cut) but I think it shouldn’t be as hard as it is

My solution: seperate to n list[column], column1, column2 … column n

then start point (S) -> column1 -> column2 -> … -> column n -> (E) end point
and implement max flow/min cut

Источник

Для заданной прямоугольной треугольной матрицы найдите сумму кратчайших путей от верхнего элемента до любого элемента в последней строке матрицы.

В любой момент времени мы можем двигаться только вниз из текущей ячейки. Следовательно, законные перемещения из ячейки (x,y) либо (x+1,y) или же (x+1,y+1). Например,

Input: mat = [
  [4],
  [1, 3],
  [1, 2, 1],
  [8, 4, 5, 1]
]

Output: 9

Explanation: The minimum path is [4, 3, 1, 1] having sum 9.

Более пристальный взгляд показывает, что эта проблема может быть рекурсивно разделена на более мелкие подзадачи, причем каждая проблема повторяется множество раз. Динамическое программирование может использоваться для решения задач с оптимальной подструктурой и перекрывающимися подзадачами.

Идея состоит в том, чтобы сохранять решения подзадач, а не повторно вычислять их. Начнем с построения двумерного массива. T[][] записывать решения подзадач, где T[i][j] будет содержать минимальный путь суммы для i-й строки и j-го столбца. Здесь, T[i][j] будет равняться сумме текущей ячейки и меньшему из сумм пути к нижней и нижней правой ячейкам. Это приводит к следующему повторению:

T[i][j] = mat[i][j] + min(T[i+1][j], T[i+1][j+1])

Например, используя повторение, описанное выше, матрица слева создаст таблицу справа. Сумма кратчайшего пути 9 и является [4, 3, 1, 1].

[4]                         [9, 0, 0, 0]
[1, 3]            —>        [6, 5, 0, 0]
[1, 2, 1]                   [5, 6, 2, 0]
[8, 4, 5, 1]                [8, 4, 5, 1]

Реализацию можно увидеть ниже на C++, Java и Python:

C++

#include <iostream>

#include <vector>

using namespace std;

int getMinimumValue(vector<vector<int>> const &mat)

{

int N = mat.size();

// взять матрицу `N x N` для хранения решений подзадачи

vector<vector<int>> T(N, vector<int>(N));

// инициализируем последнюю строку матрицы DP последней строкой матрицы

T[N—1] = mat.back();

// начинаем с предпоследней строки

for (int row = N — 2; row >= 0; row—)

{

// вычисляем T[] для каждого элемента текущей строки

for (int col = 0; col <= row; col++)

{

// T[row][col] будет суммой текущего элемента и

// минимум его нижней и нижней правой ячейки

T[row][col] = mat[row][col] + min(T[row+1][col], T[row+1][col+1]);

}

return T[0][0];

}

int main()

{

vector<vector<int>> mat = {

{4},

{1, 3},

{1, 2, 1},

{8, 4, 5, 1}

};

cout << getMinimumValue(mat);

return 0;

}

Скачать Выполнить код

результат:

9

Java

import java.util.Arrays;

class Main

{

public static int getMinimumValue(int[][] mat)

{

int N = mat.length;

// взять матрицу `N x N` для хранения решений подзадачи

int[][] T = new int[N][N];

// инициализируем последнюю строку матрицы DP последней строкой матрицы

T[N—1] = Arrays.copyOf(mat[N—1], N);

// начинаем с предпоследней строки

for (int row = N — 2; row >= 0; row—)

{

// вычисляем T[] для каждого элемента текущей строки

for (int col = 0; col <= row; col++)

{

// T[row][col] будет суммой текущего элемента и

// минимум его нижней и нижней правой ячейки

T[row][col] = mat[row][col] + Integer.min(T[row+1][col], T[row+1][col+1]);

}

return T[0][0];

}

public static void main(String[] args)

{

int[][] mat = {

{4},

{1, 3},

{1, 2, 1},

{8, 4, 5, 1}

};

System.out.println(getMinimumValue(mat));

}

Скачать Выполнить код

результат:

9

Python

def getMinimumValue(mat):

# принимает матрицу для хранения решений подзадач

T = [[0 for x in range(len(mat))] for y in range(len(mat))]

# инициализирует последнюю строку матрицы DP последней строкой матрицы

T[—1] = mat[—1]

# начать с предпоследнего ряда

for row in reversed(range(0, len(mat) — 1)):

# вычисляет T[] для каждой записи текущей строки

for col in range(0, row + 1):

# T[row][col] будет суммой текущего элемента и

# минимум его нижней и нижней правой ячейки

T[row][col] = mat[row][col] + min(T[row + 1][col], T[row + 1][col + 1])

return T[0][0]

if __name__ == ‘__main__’:

mat = [

[4],

[1, 3],

[1, 2, 1],

[8, 4, 5, 1]

]

print(getMinimumValue(mat))

Скачать Выполнить код

результат:

9

Временная сложность приведенного выше решения равна O(N × N) и требует O(N × N) дополнительное пространство, где N это количество строк в матрице.

Обратите внимание на заполнение снизу вверх. T[][] стол. Поскольку мы всегда читаем из следующей строки текущей строки, объемная сложность решения может быть уменьшена до O(N). Оптимизированный по пространству алгоритм может быть реализован на C++, Java и Python следующим образом:

C++

#include <iostream>

#include <vector>

using namespace std;

int getMinimumValue(vector<vector<int>> const &mat)

{

// инициализируем массив DP последней строкой

vector<int> T(mat.back());

// начинаем с предпоследней строки

for (int row = mat.size() — 2; row >= 0; row—)

{

// вычисляем T[] для каждого элемента текущей строки

for (int col = 0; col <= row; col++)

{

// T[col] будет суммой текущего элемента и

// минимум его нижней и нижней правой ячейки

T[col] = mat[row][col] + min(T[col], T[col + 1]);

}

return T[0];

}

int main()

{

vector<vector<int>> mat = {

{4},

{1, 3},

{1, 2, 1},

{8, 4, 5, 1}

};

cout << getMinimumValue(mat);

return 0;

}

Скачать Выполнить код

результат:

9

Java

import java.util.Arrays;

class Main

{

public static int getMinimumValue(int[][] mat)

{

int N = mat.length;

// инициализируем массив DP последней строкой

int[] T = Arrays.copyOf(mat[N—1], N);

// начинаем с предпоследней строки

for (int row = N—2; row >= 0; row—)

{

// вычисляем T[] для каждого элемента текущей строки

for (int col = 0; col <= row; col++)

{

// T[col] будет суммой текущего элемента и

// минимум его нижней и нижней правой ячейки

T[col] = mat[row][col] + Integer.min(T[col], T[col + 1]);

}

return T[0];

}

public static void main(String[] args)

{

int[][] mat = {

{4},

{1, 3},

{1, 2, 1},

{8, 4, 5, 1}

};

System.out.println(getMinimumValue(mat));

}

Скачать Выполнить код

результат:

9

Python

def getMinimumValue(mat):

# инициализирует массив DP последней строкой

T = mat[—1]

# начать с предпоследнего ряда

for row in reversed(range(0, len(mat) — 1)):

# вычисляет T[] для каждой записи текущей строки

for col in range(0, row + 1):

# T[col] будет суммой текущего элемента и

# минимум его нижней и нижней правой ячейки

T[col] = mat[row][col] + min(T[col], T[col + 1])

return T[0]

if __name__ == ‘__main__’:

mat = [

[4],

[1, 3],

[1, 2, 1],

[8, 4, 5, 1]

]

print(getMinimumValue(mat))

Скачать Выполнить код

результат:

9

Временная сложность приведенного выше решения равна O(N × N) и требует O(N) дополнительное пространство, где N это количество строк в матрице.

Источник

const
  n=10;
 
type
  TMatr = array [1..n,1..n] of Real;
 
function MinRowSum(const m: TMatr): Real;
var
  i, j: Integer;
  s, r: Real;
begin
  r:=0;
  for j:=1 to n do r:=r+m[1,j];
  for i:=2 to n do begin
    s:=0; for j:=1 to n do s:=s+m[i,j];
    if r>s then r:=s;
  end;
  MinRowSum:=r;
end;
{ отладочная часть }
var
  a: TMatr;
  i, j: Integer;
  s: Real;
begin
  Randomize;
  for i:=1 to n do begin
    s:=0;
    for j:=1 to n do begin
      a[i,j]:=-50+Random(101); s:=s+a[i,j]; Write(a[i,j]:4:0);
    end; WriteLn('|',s:6:0);
  end;
  WriteLn('Минимальная сумма строки: ',MinRowSum(a):6:0);
end.

Источник

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

example 1:
[[1, 2, 3], 

 [1, 2, 3], 

 [3, 3, 1]]

minimum sum = 1 + 2 + 1 = 4  // matrix[0][0] + matrix[1][1] + matrix[2][2] or matrix[0][1] + matrix[1][0] + matrix[2][2]

example 2:
[[1, 100, 1], 

 [2, 99, 30],

 [100, 12, 13]]

minimum sum = 1 + 2 + 12 = 15 // matrix[0][2] + matrix[1][0] + matrix[2][1]

example 3:
[[1, 2, 3], 

 [2, 5, 4],

 [2, 3, 1],

 [1, 6, 3]]

minimum sum = 2 + 2 + 1 + 1 = 6 // matrix[0][1] + matrix[1][0] + matrix[2][2] + matrix[3][0]

Вот мой код:

    public static int minCost(List<List<Integer>> matrix) {
        // Write your code here
        int rows = matrix.size();

        int[] cost = findMin(matrix.get(0), -1);
        int total = cost[0];

        for (int i = 1; i < rows; i++){
            List<Integer> row = matrix.get(i);
            cost = findMin(row, cost[1]);
            total += cost[0];
        }
        return total;
    }

    private static int[] findMin(List<Integer> row, int col){
        int[] ans = new int[2];
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < row.size(); i++) {
            if (i == col){
                continue;
            }
            if (row.get(i) < min) {
                min = row.get(i);
                ans[0] = min;
                ans[1] = i;
            }
        }
        return ans;
    }

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

Этот метод не подходит для примеров 2 и 3. Я думаю, что динамическое программирование было бы подходом к решению этой проблемы, но я не уверен, как построить часть mem. Как на самом деле решить эту проблему с помощью динамического программирования? Заранее спасибо!

2 ответа

Лучший ответ

Да, вам нужно определить рекурсивную структуру, как вы указали в одном из своих комментариев.

Вы можете определить следующее: Допустим, вы в настоящее время находитесь в строке row, а предыдущий выбранный вами столбец был prevcol, тогда вам нужно выбрать значение, которого нет в предыдущем столбце, и выполнить рекурсию по оставшимся строкам и получить минимум все такие значения, т.е. каждый раз, когда вы выбираете столбец, который не является предыдущим столбцом, и рекурсивно просматриваете оставшиеся строки, указывая, что предыдущий выбранный столбец был тем столбцом, который вы выбрали только что.

Посмотрите на это рекурсивное уравнение, чтобы понять больше:

f( arr, row, prevcol ) = minimum of ( for all col not equal to prevcol ( arr[row][col] + f( arr, row + 1, col ) )

Вы видите, как указать следующую строку и предыдущий столбец, выбранные в вызове f(arr, row +1, col )?

Базовое условие: если row == arr.length, т.е. не осталось строк, то результатом будет 0.

И вы запоминаете значения, которые получаете для каждой комбинации row и prevcol

Код Java будет:

private static int f( int[][] arr, int row, int prevCol ) {
    if ( row == arr.length ) return 0;

    int C = arr[row].length;
    if ( dp[row][prevCol+1] != Integer.MAX_VALUE ) return dp[row][prevCol+1];
    int res = Integer.MAX_VALUE;
    for ( int j = 0; j < C; j++ ) {
      if ( j != prevCol ) {
        int val = arr[row][j] + f ( arr, row + 1, j );
        res = Math.min ( res, val );
      }
    }
    dp[row][prevCol+1] = res;
    return res;
  }

Вам нужно создать экземпляр массива dp, например:

dp = new int[arr.length][arr[0].length+1];
for ( int[] r : dp ) Arrays.fill(r, Integer.MAX_VALUE);

И вы вызываете функцию как: f( arr, 0, -1 ), где 0 — это начальный row, а -1 — prevcol. Поскольку prevcol начинается с -1, вам необходимо сохранить значение в dp[row][prevcol+1]

А также для вашего третьего примера ответ 6 не 9.

row = 0, col = 1 : 2
row = 1, col = 0 : 2
row = 2, col = 2 : 1
row = 3, col = 0 : 1
2 + 2 + 1 + 1 = 6

SomeDude
6 Фев 2020 в 23:00

Большое спасибо @SomeDude Это моя реализация того же самого на Python.

import math
def mincost(arr,row,prevcol,n,k):
    if row == len(arr):
        return 0
    C = len(arr[row])
    dp = [[math.inf for x in range(k+1)] for y in range(n)]
    if dp[row][prevcol+1] != math.inf:
        return dp[row][prevcol+1]
    res = math.inf
    for j in range(C):
        if j != prevcol:
            val = arr[row][j] + mincost(arr,row+1,j,n,k)
            res = min(res,val)
    dp[row][prevcol+1] = res
    return res

Я проверил все приведенные выше тестовые примеры, указанные @bonus, он работает.

Vikas Chitturi
24 Май 2020 в 20:26

Источник