Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
kalaider
0 / 0 / 0
Регистрация: 24.10.2012
Сообщений: 31
#1

Выбор оптимальной последовательности. Конечный алгоритм - C++

03.01.2013, 22:14. Просмотров 563. Ответов 10
Метки нет (Все метки)

Дана квадратная матрица размером NxN, например:
[0, 2, 0, 0]
[0, 0, 3, 0]
[0, 0, 0, 1]
[3, 1, 1, 1]
Нужно выбрать j-е число из i-ой строки, чтобы j был уникален, т.е. если из первой строки выбрать число на первом месте, то из второй, третьей, четвертой и т.д. первое число выбрать уже нельзя. Задача: выбрать такие числа, чтобы их сумма была максимальной.
В данном примере макс. сумма будет 2 + 3 + 1 + 3 = 9

Добавлено через 23 часа 46 минут
Хотелось бы увидеть реализацию метода динамического программирования для этой задачи. Полный перебор мной уже реализован, но для больших матриц он слишком медленный. Я с динамическим программированием знаком не слишком хорошо, так что самому написать сложно.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.01.2013, 22:14
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Выбор оптимальной последовательности. Конечный алгоритм (C++):

Выбор оптимальной структуры данных - C++
Здравствуйте! Задача состоит в следующем. Есть большой файл (~68 mb) с текстом. Нужно посчитать сколько раз встречается каждое слово...

Многопоточность и вычисления: выбор оптимальной стратегии - C++
Есть некоторый массив float acc Нужно произвести модификацию элементов этого массива, путём многократного прибавления(M>>SIZE)...

Выбор цифры из последовательности - C++
Есть задача: С клавиатуры ввести натуральное k. Вывести k-ю цифру последовательности 1234567891011121314151617…, в которой выписаны...

Разветвляющийся алгоритм (выбор по условию). - C++
Здравствуйте!!! Помогите пожалуйста с задачей. TC++ Лежат ли обе точки D(a1;b1) и C(a2;b2) внутри круга радиуса R с центром в начале...

Последовательности чисел: как улучшить / ускорить алгоритм? - C++
Задание: Для заданной последовательности неотрицательных целых чисел необходимо найти максимальное произведение двух её элементов,...

Составить алгоритм определения последовательности номеров удаляемых спортсменов - C++
ребята! до завтра ришите задачу. пожалуйста. я ноль в программировании по кругу стоят N спортсменов с номерами от 1 до N. начиная с...

10
Nixy
ComfyMobile
400 / 281 / 8
Регистрация: 24.07.2012
Сообщений: 916
03.01.2013, 23:23 #2
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
 #include <iostream>
 #include <math.h>
 #include "windows.h"
 
 using namespace std;
 
 
 
 int main()
 {
     SetConsoleCP(1251);
     SetConsoleOutputCP(1251);
     double ** matrix;
     double sum = 0;
     int size;
     cout << "Введите ращмер матрицы " ;
     cin >> size;
     matrix = new double* [size];
 
     for (int i = 0; i < size; i++) {
         matrix[i] = new double [size];
         double max = -1.7E308;  //наименьшее число типа double
         for (int j = 0; j < size; j++) {
             cout<< "Введите matrix[" << i << "][" << j << "] ";
             cin >> matrix[i][j] ;
             max = max < matrix[i][j] ? matrix[i][j] : max;
         }
         sum += max;
     }
     for (int i = 0; i < size; i++) {
        for (int j = 0; j < size; j++) {
           cout << matrix[i][j] << " " ;
        }
        cout << endl;
     }
     cout << "Наибольшая сумма " << sum<<endl;
     system("pause");
     return 0;
 }
1
kalaider
0 / 0 / 0
Регистрация: 24.10.2012
Сообщений: 31
04.01.2013, 13:50  [ТС] #3
Это немного не то: у Вас не учтено, что j не может повторяться. В этом случае максимальная сумма будет зависеть от порядка строк. У меня только перебором получилось.
0
Nixy
ComfyMobile
400 / 281 / 8
Регистрация: 24.07.2012
Сообщений: 916
04.01.2013, 14:48 #4
а понял, щас добавлю

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
 #include <iostream>
 #include <math.h>
 #include "windows.h"
 
 using namespace std;
 
 bool isMax(int row,int col,int size,double ** matrix){
 
    for (int i = 0; i < size; i++) {  // максимум в столбце
        if (matrix[row][col] < matrix[i][col]) {
            return false;
        }
    }
 
    for (int j = 0; j < size; j++) {   // максимум в строке
        if (matrix[row][col] < matrix[row][j]) {
            return false;
        }
    }
    return true;
 
 }
 
 int main()
 {
     SetConsoleCP(1251);
     SetConsoleOutputCP(1251);
     double ** matrix;
     double sum = 0;
     int size;
     int count = 0;
     cout << "Введите ращмер матрицы " ;
     cin >> size;
     matrix = new double* [size];
 
     for (int i = 0; i < size; i++) {
         matrix[i] = new double [size];
         for (int j = 0; j < size; j++) {
             cout<< "Введите matrix[" << i << "][" << j << "] ";
             cin >> matrix[i][j] ;
         }
     }
 
      for (int i = 0; i < size; i++) {
        for (int j = 0; j < size; j++) {
           cout << matrix[i][j] << " " ;
        }
        cout << endl;
     }
     cout << endl;
     while (count < size) { //флаг на случай если с 1 раза не все очевидно
         for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                if (isMax(i,j,size,matrix)) {
                   for (int k = 0; k < size; k++) {
                       if (k!=i) {
                         matrix[k][j] = -1.7E-308;
                       }
                    for (int k = 0; k < size; k++) {
                       if (k!=j) {
                         matrix[i][k] = -1.7E-308;
                       }
                    }
                   }
                   sum += matrix[i][j];
                   count++;
                }
            }
 
         }
     }
     for (int i = 0; i < size; i++) {
        for (int j = 0; j < size; j++) {
           if (matrix[i][j] == -1.7E-308) {
               matrix[i][j] = 0;
           }
        }
     }
     cout << endl;
     for (int i = 0; i < size; i++) {
        for (int j = 0; j < size; j++) {
           cout << matrix[i][j] << " " ;
        }
        cout << endl;
     }
     cout << "Наибольшая сумма " << sum<<endl;
     system("pause");
     return 0;
 }
1
kalaider
0 / 0 / 0
Регистрация: 24.10.2012
Сообщений: 31
04.01.2013, 20:36  [ТС] #5
[удалено]

Добавлено через 8 минут
Ваш алгоритм не дает точного решения, например, в таком случае:
[8, 9]
[0, 8]
Ваш ответ: 9
Нужный: 16
0
Nixy
ComfyMobile
400 / 281 / 8
Регистрация: 24.07.2012
Сообщений: 916
04.01.2013, 22:11 #6
тогда покажите ваш перебор на чем он основан
0
kalaider
0 / 0 / 0
Регистрация: 24.10.2012
Сообщений: 31
04.01.2013, 23:29  [ТС] #7
Вот мой Java-код (просто изначально писал на Java, думаю, будет понятно):
Java
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
    private int size;
    private int[][] matrix;
    private int max;
    
    //В main: ввод size, matrix; max = 0;
    
    public void compute(boolean[] usages
                                        int current,
                                        int i) {
        if (i >= size) {
            return;
        }
        int temp;
        for (int j = 0; j < n; j++) {
            if (usages[j]) {
                continue;
            }
            temp = current;
            current += matrix[i][j];
            usages[j] = true;
            max = Math.max(current, max);
            if (i < size) {
                compute(usages, current, i + 1);
            }
            current = temp;
            usages[j] = false;
        }
    }
0
Nixy
ComfyMobile
400 / 281 / 8
Регистрация: 24.07.2012
Сообщений: 916
04.01.2013, 23:40 #8
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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
#include <iostream>
#include "windows.h"
 
 
using namespace std;
 
bool isMaxX(int row,int col,int size,double ** matrix){
 
    for (int i = 0; i < size; i++) {  // максимум в столбце
        if (matrix[row][col] < matrix[i][col]) {
            return false;
        }
    }
 
    for (int j = 0; j < size; j++) {   // максимум в строке
        if (matrix[row][col] < matrix[row][j]) {
            return false;
        }
    }
    return true;
 
 }
bool isMaxR(int row,int col,int size,double ** matrix){
 
    for (int j = 0; j < size; j++) {   // максимум в строке
        if (matrix[row][col] < matrix[row][j]) {
            return false;
        }
    }
    return true;
 
 }
bool isMaxC(int row,int col,int size,double ** matrix){
 
    for (int i = 0; i < size; i++) {  // максимум в столбце
        if (matrix[row][col] < matrix[i][col]) {
            return false;
        }
    }
 
    return true;
 
 }
 
double getSum(double ** matrix,int size,bool  flag(int,int,int,double**)){
    int count = 0;
    double sum = 0;
    while (count < size) { //флаг на случай если с 1 раза не все очевидно
         for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                if (flag(i,j,size,matrix)) {
                   for (int k = 0; k < size; k++) {
                       if (k!=i) {
                         matrix[k][j] = -1.7E-308;
                       }
                    for (int k = 0; k < size; k++) {
                       if (k!=j) {
                         matrix[i][k] = -1.7E-308;
                       }
                    }
                   }
                   sum += matrix[i][j];
                   count++;
                }
            }
 
         }
     }
     return sum;
}
 
 int main()
 {
     SetConsoleCP(1251);
     SetConsoleOutputCP(1251);
     double ** matrix;
     double ** tmp;
     double sum1,sum2,sum3,ressum;
     int size;
 
     cout << "Введите ращмер матрицы " ;
     cin >> size;
     matrix = new double* [size];
     tmp = new double* [size];
     for (int i = 0; i < size; i++) {
         matrix[i] = new double [size];
         tmp[i] = new double [size];
         for (int j = 0; j < size; j++) {
             cout<< "Введите matrix[" << i << "][" << j << "] ";
             cin >> matrix[i][j] ;
 
         }
     }
 
      for (int i = 0; i < size; i++) {
        for (int j = 0; j < size; j++) {
           cout << matrix[i][j] << " " ;
           tmp[i][j] = matrix[i][j];
        }
        cout << endl;
     }
     cout << endl;
 
     sum1 = getSum(tmp,size,&isMaxX);   // расчет суммы на основе перекрестныъ
 
      for (int i = 0; i < size; i++) {      //привидение tmp к исходному
        for (int j = 0; j < size; j++) {
           tmp[i][j] = matrix[i][j];
        }
     }
     sum2 = getSum(tmp,size,&isMaxR);   // расчет суммы на основе строк
 
     for (int i = 0; i < size; i++) {     //привидение tmp к исходному
        for (int j = 0; j < size; j++) {
           tmp[i][j] = matrix[i][j];
        }
     }
     sum3 = getSum(tmp,size,&isMaxC);  // расчет суммы на основе столбцов
 
     if (sum1 > sum2 ) {
       if (sum1 > sum3) {
          ressum = getSum(matrix,size,&isMaxX);   //перекрестная
       } else{
          ressum = getSum(matrix,size,&isMaxC);   // колонки
       }
     }else{
         if (sum2 > sum3) {
            ressum = getSum(matrix,size,&isMaxR);   // строки
         }else {
            ressum = getSum(matrix,size,&isMaxC);   // колонки
         }
     }
     for (int i = 0; i < size; i++) {
        for (int j = 0; j < size; j++) {
           if (matrix[i][j] == -1.7E-308) {
               matrix[i][j] = 0;
           }
        }
     }
     cout << endl;
     for (int i = 0; i < size; i++) {
        for (int j = 0; j < size; j++) {
           cout << matrix[i][j] << " " ;
        }
        cout << endl;
     }
     cout << "Наибольшая сумма " << ressum<<endl;
     system("pause");
     return 0;
 }
ну вот тогда этот потестите

Добавлено через 4 минуты

Не по теме:

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

1
kalaider
0 / 0 / 0
Регистрация: 24.10.2012
Сообщений: 31
04.01.2013, 23:50  [ТС] #9
Цитата Сообщение от Nixy Посмотреть сообщение
Не по теме:
эх столько бьюсь над задачкой а вы даже спасибо не кликнули, мелочь но приятно)
Вот будет работать, кликну
0
Nixy
04.01.2013, 23:51
  #10

Не по теме:

ха интересный вы человек, ну ладно,знал бы что вы скряга не стал бы помогать

0
kalaider
0 / 0 / 0
Регистрация: 24.10.2012
Сообщений: 31
04.01.2013, 23:54  [ТС] #11
Вроде работает. Спасибо!!!
Теперь буду разбираться и оптимизировать под себя.
0
04.01.2013, 23:54
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
04.01.2013, 23:54
Привет! Вот еще темы с ответами:

Алгоритм поиска элемента последовательности, не являющегося элементом второй - C++
Доброго времени суток! Выполняя очередную лабораторную по программированию, наткнулся на проблему выбора наиболее быстрого алгоритма для...

Жадный алгоритм для определения последовательности обхода городов. - C++
Здравствуйте! Изучаю разные транспортные алгоритмы и возник следующий вопрос. На основе данных, полученных из txt-файла формирую...

Найти счёт при оптимальной стратегии двух игроков - C++
взялся тут решать задачку с олимпиады, и честно говоря уже час потратил за зря...Никак не могу продумать сам алгоритм игры игроков... ...

Эмуляция планировщика процессов с использованием волокон. Алгоритм "случайный выбор" - C++
Прошу помочь.Есть готовая программа(готовый код).Хочу знать, что значит каждая строка кода. Для написания курсовой работы. using...


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

Или воспользуйтесь поиском по форуму:
11
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru