Форум программистов, компьютерный форум CyberForum.ru

В матрице выбрать n элементов в разных строках и разных столбцах так, чтобы их сумма была минимальной - C++

Восстановить пароль Регистрация
 
Natasha_152
0 / 0 / 0
Регистрация: 03.06.2013
Сообщений: 20
10.01.2014, 22:34     В матрице выбрать n элементов в разных строках и разных столбцах так, чтобы их сумма была минимальной #1
Помогите,пожалуйста

Добавлено через 2 часа 23 минуты
примерный алгоритм как это можно сделать
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
10.01.2014, 22:34     В матрице выбрать n элементов в разных строках и разных столбцах так, чтобы их сумма была минимальной
Посмотрите здесь:

Определить, является ли заданная матрица N-го порядка магическим квадратом, т.е. такой, в которой сумма элементов во всех строках и столбцах одинакова C++
Сумма элементов матрицы,стоящих в четных столбцах и нечетных строках. На C++. C++
Разложить камни на 2 кучки так, чтобы разница масс этих кучек была минимальной. C++
Как сделать, чтобы в окне программы при запуске переменные стояли на разных строках? C++
C++ Рекурсия: найти непрерывную часть массива, чтобы сумма элементов была максимальной
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
__General__
24 / 24 / 3
Регистрация: 04.01.2014
Сообщений: 91
Завершенные тесты: 2
10.01.2014, 22:56     В матрице выбрать n элементов в разных строках и разных столбцах так, чтобы их сумма была минимальной #2
Первое что приходит в голову - перебрать все такие суммы (ну, по всевозможным перестановкам) и выбрать минимальную.

Правда, такая программа будет работать очень медленно (O(n!)).
TrueBit
 Аватар для TrueBit
95 / 95 / 12
Регистрация: 19.11.2012
Сообщений: 195
10.01.2014, 23:23     В матрице выбрать n элементов в разных строках и разных столбцах так, чтобы их сумма была минимальной #3
main.cpp:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <iostream>
#include <vector>
#include <set>
#include <ctime>
#include <stdlib.h>
#include <stdio.h>
using namespace std;
 
int main() {
    vector< vector<int> > matrix;
    multiset<int> min_elements;
    int sum=0;
    int n;
    srand((unsigned int)time(NULL));
 
    cout << "n = "; cin >> n;
    // vector resize
    matrix.resize(n);
    for(vector< vector<int> >::iterator i=matrix.begin(); i!=matrix.end(); i++)
        (*i).resize(n);
 
    // fill vector rand
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            matrix[i][j]=rand()%100;
 
    // print vector
    printf("Matrix: \n");
    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++)
            printf("%3d ",matrix[i][j]);
        printf("\n");
    }
 
    // fill multiset
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++) {
            if(min_elements.size() < (size_t)n)
                min_elements.insert(matrix[i][j]);
            else if(*min_elements.rbegin() > matrix[i][j]) {
                min_elements.erase(min_elements.find(*min_elements.rbegin()));
                min_elements.insert(matrix[i][j]);
            }
        }
 
    // print multiset
    printf("Minimum elements: \n");
    for(multiset<int>::iterator i=min_elements.begin(); i!=min_elements.end(); i++) {
        printf("%d ",(*i));
        sum+=(*i);
    }
    printf("\n");
 
    printf("Sum elements: %d\n", sum);
 
}
out:
Код
./untitled 
n = 5
Matrix: 
 67  64  74  38  69 
 84  37  77  16  18 
 46  16  58  68  76 
 11  27  55  97  76 
 88   0   5  81  22 
Minimum elements: 
0 5 11 16 16 
Sum elements: 48
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
10.01.2014, 23:28     В матрице выбрать n элементов в разных строках и разных столбцах так, чтобы их сумма была минимальной #4
TrueBit, по вашему 0 и 5 в разных строках и столбцах находятся?
TrueBit
 Аватар для TrueBit
95 / 95 / 12
Регистрация: 19.11.2012
Сообщений: 195
11.01.2014, 01:00     В матрице выбрать n элементов в разных строках и разных столбцах так, чтобы их сумма была минимальной #5
Цитата Сообщение от Dani Посмотреть сообщение
TrueBit, по вашему 0 и 5 в разных строках и столбцах находятся?
Извиняюсь, неправильно прочитал условие задачи.

По задаче: Я думаю тут можно использовать формулы вычисления определителей, ведь каждое слагаемое определителя по определению должно содержать элементы матрицы расположенные в различных строках и различных столбцах, и эти слагаемые вычисляются по известным формулам. То есть необязательно перебирать всю матрицу, а достаточно найти минимальное число, составленное путем суммирования элементов очередного слагаемого в формуле определителя.
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
11.01.2014, 01:03     В матрице выбрать n элементов в разных строках и разных столбцах так, чтобы их сумма была минимальной #6
Если по этой задаче организовывать перебор, то он будет похож на перебор для задачи "Расстановка n ферзей на доске n*n"
kidpoker
 Аватар для kidpoker
6 / 5 / 0
Регистрация: 02.08.2012
Сообщений: 16
11.01.2014, 01:16     В матрице выбрать n элементов в разных строках и разных столбцах так, чтобы их сумма была минимальной #7
Пока так получилось, нужно что-то придумать чтобы не только для N=3 работало, а для любой + выделить из полученных наименьшую, ну это просто главное первую проблему решить.

Вообще, должен быть какой то алгоритм, под чей то фамилией.

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <iostream>
#include <conio.h>
using namespace std;
#define N 3
#define MAX_VALUE 1000
 
int _tmain(int argc, _TCHAR* argv[])
{
    int matrix[N][N];
 
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            matrix[i][j]=rand()%MAX_VALUE;
            printf("%d ", matrix[i][j]);
        }
         
        puts("");
    }
 
    /*
    int comb=1;
    for(int i=1;i<=N;i++)
        comb*=i;*/
 
    //printf("N = %d comb = %d \n", N, comb);
    int res[N]={0}, resI=0;
 
 
    for (int i=0; i<N; i++){
        for (int j=0; j<N; j++){
            for (int k=0; k<N; k++){
                if ((i!=j)&&(j!=k)&&(i!=k)){
                    int sum=matrix[0][i]+matrix[1][j]+matrix[2][k];
                    printf("%d %d %d sum: %d\n",i,j,k,sum);
                    //res[resI]=sum;
                }
            }
        }
    }
 
    getch();
    return 0;
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.01.2014, 01:19     В матрице выбрать n элементов в разных строках и разных столбцах так, чтобы их сумма была минимальной
Еще ссылки по теме:

C++ сделать так, чтобы при разных значениях cin, выводились разные сообщения
Считает элементы в строках а не столбцах. Что не так? C++
C++ Отсортировать строки массива так, чтобы первой шла строка, сумма элементов которой была меньше, чем остальных

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
11.01.2014, 01:19     В матрице выбрать n элементов в разных строках и разных столбцах так, чтобы их сумма была минимальной #8
kidpoker, три цикла в коде напоминают алгоритм Флойда
Yandex
Объявления
11.01.2014, 01:19     В матрице выбрать n элементов в разных строках и разных столбцах так, чтобы их сумма была минимальной
Закрытая тема Создать тему
Опции темы

Текущее время: 00:39. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru