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

@kalaider · Регистрация: 24.10.2012

Author24 — интернет-сервис помощи студентам

Дана квадратная матрица размером 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 минут
Хотелось бы увидеть реализацию метода динамического программирования для этой задачи. Полный перебор мной уже реализован, но для больших матриц он слишком медленный. Я с динамическим программированием знаком не слишком хорошо, так что самому написать сложно.

@Nixy · 03.01.2013, 23:23

C++

 #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 · 04.01.2013, 13:50 **[ТС]**

Это немного не то: у Вас не учтено, что j не может повторяться. В этом случае максимальная сумма будет зависеть от порядка строк. У меня только перебором получилось.

@Nixy · 04.01.2013, 14:48

а понял, щас добавлю

C++

 #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 · 04.01.2013, 20:36 **[ТС]**

[удалено]

Добавлено через 8 минут
Ваш алгоритм не дает точного решения, например, в таком случае:
[8, 9]
[0, 8]
Ваш ответ: 9
Нужный: 16

@Nixy · 04.01.2013, 22:11

тогда покажите ваш перебор на чем он основан

@kalaider · 04.01.2013, 23:29 **[ТС]**

Вот мой Java-код (просто изначально писал на Java, думаю, будет понятно):

Java

    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 · 04.01.2013, 23:40

C++

#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 · 04.01.2013, 23:50 **[ТС]**

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

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

Вот будет работать, кликну

@Nixy · 04.01.2013, 23:51

Не по теме:

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

@kalaider · 04.01.2013, 23:54 **[ТС]**

Вроде работает. Спасибо!!!
Теперь буду разбираться и оптимизировать под себя.

@kalaider 0 / 0 / 1 Регистрация: 24.10.2012 Сообщений: 31
		1
	Выбор оптимальной последовательности. Конечный алгоритм 03.01.2013, 22:14. Показов 902. Ответов 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

@kalaider 0 / 0 / 1 Регистрация: 24.10.2012 Сообщений: 31
	04.01.2013, 13:50 [ТС]	3
	Это немного не то: у Вас не учтено, что j не может повторяться. В этом случае максимальная сумма будет зависеть от порядка строк. У меня только перебором получилось. 0

@kalaider 0 / 0 / 1 Регистрация: 24.10.2012 Сообщений: 31
	04.01.2013, 20:36 [ТС]	5
	[удалено] Добавлено через 8 минут Ваш алгоритм не дает точного решения, например, в таком случае: [8, 9] [0, 8] Ваш ответ: 9 Нужный: 16 0

@Nixy ComfyMobile 401 / 282 / 34 Регистрация: 24.07.2012 Сообщений: 916
	04.01.2013, 22:11	6
	тогда покажите ваш перебор на чем он основан 0

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

@Nixy
	04.01.2013, 23:51 #10
	Не по теме: ха интересный вы человек, ну ладно,знал бы что вы скряга не стал бы помогать :( 0

@kalaider 0 / 0 / 1 Регистрация: 24.10.2012 Сообщений: 31
	04.01.2013, 23:54 [ТС]	11
	Вроде работает. Спасибо!!! Теперь буду разбираться и оптимизировать под себя. 0