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

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

Восстановить пароль Регистрация
 
kalaider
0 / 0 / 0
Регистрация: 24.10.2012
Сообщений: 31
03.01.2013, 22:14     Выбор оптимальной последовательности. Конечный алгоритм #1
Дана квадратная матрица размером 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 минут
Хотелось бы увидеть реализацию метода динамического программирования для этой задачи. Полный перебор мной уже реализован, но для больших матриц он слишком медленный. Я с динамическим программированием знаком не слишком хорошо, так что самому написать сложно.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.01.2013, 22:14     Выбор оптимальной последовательности. Конечный алгоритм
Посмотрите здесь:

C++ Разветвляющийся алгоритм (выбор по условию).
Жадный алгоритм для определения последовательности обхода городов. C++
C++ Эмуляция планировщика процессов с использованием волокон. Алгоритм "случайный выбор"
Составить алгоритм определения последовательности номеров удаляемых спортсменов C++
C++ составить алгоритм нахождения всех неотрицательных чисел стоящих на четных местах в последовательности х1, х2,
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Nixy
ComfyMobile
 Аватар для Nixy
399 / 280 / 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;
 }
kalaider
0 / 0 / 0
Регистрация: 24.10.2012
Сообщений: 31
04.01.2013, 13:50  [ТС]     Выбор оптимальной последовательности. Конечный алгоритм #3
Это немного не то: у Вас не учтено, что j не может повторяться. В этом случае максимальная сумма будет зависеть от порядка строк. У меня только перебором получилось.
Nixy
ComfyMobile
 Аватар для Nixy
399 / 280 / 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;
 }
kalaider
0 / 0 / 0
Регистрация: 24.10.2012
Сообщений: 31
04.01.2013, 20:36  [ТС]     Выбор оптимальной последовательности. Конечный алгоритм #5
[удалено]

Добавлено через 8 минут
Ваш алгоритм не дает точного решения, например, в таком случае:
[8, 9]
[0, 8]
Ваш ответ: 9
Нужный: 16
Nixy
ComfyMobile
 Аватар для Nixy
399 / 280 / 8
Регистрация: 24.07.2012
Сообщений: 916
04.01.2013, 22:11     Выбор оптимальной последовательности. Конечный алгоритм #6
тогда покажите ваш перебор на чем он основан
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;
        }
    }
Nixy
ComfyMobile
 Аватар для Nixy
399 / 280 / 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 минуты

Не по теме:

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

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

Не по теме:

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

MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
04.01.2013, 23:54     Выбор оптимальной последовательности. Конечный алгоритм
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
kalaider
0 / 0 / 0
Регистрация: 24.10.2012
Сообщений: 31
04.01.2013, 23:54  [ТС]     Выбор оптимальной последовательности. Конечный алгоритм #11
Вроде работает. Спасибо!!!
Теперь буду разбираться и оптимизировать под себя.
Yandex
Объявления
04.01.2013, 23:54     Выбор оптимальной последовательности. Конечный алгоритм
Ответ Создать тему
Опции темы

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