Сортировка. Двумерный массив. Перестановки

[voron]

Дан массив m[7][3]. Массив заполняется вручную. Необходимо разместить элементы так, чтобы сумма каждого столбца была одинаковой. Т.е. если a среднее то равно сумме всех элементов деленных на количество столбцов т.е. 3 и сумма каждого столбца
должна быть равной среднему а.
Задача решена, только работает не совсем правильно.
Вот часть кода где происходит вычисление:

Добавлено через 1 час, 20 минут и 57 секунд:

Код: (C++)

const int r=7;
const int c=3;
int imi=0;
int ima=0;
int total=1;
int counter=0;
double sum=0;
double average=0;
double min=0,max=0;
double k=0;
double trash=0;
double m[r][c];
double mr1[r][r];
double sc[c];
double e[c];
double b1[r];
double b2[r];
double b3[r];


imi=0;  //минимальный столбец
ima=0;  //максимальный столбец
total=1;
counter=0;
sum=0;  //сумма
average=0;      //среднее
min=0,max=0;
k=0;
//считаем сумму
for(int j=0;j<c;j++)
for(int i=0;i<r;i++)
{sum+=m[i][j];}

label1:
for(int i=0;i<c;i++)   {sc[i]=0;}
for(int i=0;i<c;i++)   {e[i]=0;}
counter=1;
//       Построим матрицу
Form1->Label6->Caption=m[0][0];
Form1->Label9->Caption=m[1][0];
Form1->Label12->Caption=m[2][0];
Form1->Label15->Caption=m[3][0];
Form1->Label18->Caption=m[4][0];
Form1->Label21->Caption=m[5][0];
Form1->Label24->Caption=m[6][0];
Form1->Label4->Caption=m[0][1];
Form1->Label7->Caption=m[1][1];
Form1->Label10->Caption=m[2][1];
Form1->Label13->Caption=m[3][1];
Form1->Label16->Caption=m[4][1];
Form1->Label19->Caption=m[5][1];
Form1->Label22->Caption=m[6][1];
Form1->Label5->Caption=m[0][2];
Form1->Label8->Caption=m[1][2];
Form1->Label11->Caption=m[2][2];
Form1->Label14->Caption=m[3][2];
Form1->Label17->Caption=m[4][2];
Form1->Label20->Caption=m[5][2];
Form1->Label23->Caption=m[6][2];
//Вычислим сумму каждого столбца
for(int j=0;j<c;j++)
for(int i=0;i<r;i++)
{sc[j]+=m[i][j];}
Form1->Label27->Caption=sc[0];
Form1->Label25->Caption=sc[1];
Form1->Label26->Caption=sc[2];
//Вычислим среднюю сумму элементов каждого столбца
average=sum/c;
Form1->Label28->Caption=average;
// Вычислим отклонение суммы каждого столбца
// от средней суммы
for(int i=0;i<c;i++){e[i]=sc[i]-average;}
Form1->Label31->Caption=e[0];
Form1->Label29->Caption=e[1];
Form1->Label30->Caption=e[2];
//Находим минимальный и максимальный
min=0; min=e[0]; imi=0;
if(min>e[1]){min=e[1]; imi=1;}
if(min>e[2]){min=e[2]; imi=2;}
max=0; max=e[0]; ima=0;
if(max<e[1]){max=e[1]; ima=1;}
if(max<e[2]){max=e[2]; ima=2;}
//критерий поиска
if(min<0){k=-min-int(min);//отделим десятые от целого
/*if(k==0){k=-min/2;} */
}
if(k!=0)
{
do
{
for(int i=0;i<r;i++)//и минимального стб
for(int j=0;j<r;j++)
{
mr1[j][i]=m[i][ima]-m[j][imi];//здесь все возможные варианты разностей
                                        //элементов
if(mr1[j][i]>0&&mr1[j][i]<=k)//ищем соответствие для перестановки
{
double temp=0;
temp=m[i][ima];
m[i][ima]=m[j][imi];
m[j][imi]=temp;
if((e[0]!=0)&&(e[1]!=0)&&(e[2]!=0))
{goto label1;}//если уверждение верно значит считаем заново
//говорит что прошел проверку
}
//гуляем
counter++;//считаем
//считем до 50 и считаем все заново
if(counter>50){counter=0;goto label1;}
for(int i=0;i<c;i++){sc[i]=0;}//обнуляем сумму
for(int j=0;j<c;j++)//столбцы
for(int i=0;i<r;i++){sc[j]+=m[i][j];}//сумма
for(int i=0;i<c;i++){e[i]=0;e[i]=sc[i]-average;}//отклонение
if(counter>=50){goto label2;}//выход из бесконечности и выдача результатов
}
}while((e[0]!=0)&&(e[1]!=0)&&(e[2]!=0));
} //end if k
//Конечная матрица элементов
label2:
//Делаем балансировку в столбцe1
for(int i=0;i<=r;i++){ b1[i]=0;}
for(int i=0;i<r;i++){b1[i]=m[i][0];}
for(int u=1;u<r;u++)
{
for(int j=0;j<r-u;j++)
{
if(b1[j]>b1[j+1])
{
trash=0;
trash=b1[j];
b1[j]=b1[j+1];
b1[j+1]=trash;
}
}
}
//проверяем
m[0][0]=b1[6];
m[1][0]=b1[4];
m[2][0]=b1[2];
m[3][0]=b1[0];
m[4][0]=b1[1];
m[5][0]=b1[3];
m[6][0]=b1[5];
//Делаем балансировку в столбцe2
for(int i=0;i<=r;i++){ b2[i]=0;}
for(int i=0;i<r;i++){b2[i]=m[i][1];}
for(int u=1;u<r;u++)
{
for(int j=0;j<r-u;j++)
{
if(b2[j]>b2[j+1])
{
trash=0;
trash=b2[j];
b2[j]=b2[j+1];
b2[j+1]=trash;
}
}
}
//проверяем
m[0][1]=b2[6];
m[1][1]=b2[4];
m[2][1]=b2[2];
m[3][1]=b2[0];
m[4][1]=b2[1];
m[5][1]=b2[3];
m[6][1]=b2[5];
//Делаем балансировку в столбцe3
for(int i=0;i<=r;i++){ b3[i]=0;}
for(int i=0;i<r;i++){b3[i]=m[i][2];}
for(int u=1;u<r;u++)
{
for(int j=0;j<r-u;j++)
{
if(b3[j]>b3[j+1])
{
trash=0;
trash=b3[j];
b3[j]=b3[j+1];
b3[j+1]=trash;
}
}
}
//проверяем
m[0][2]=b3[6];
m[1][2]=b3[4];
m[2][2]=b3[2];
m[3][2]=b3[0];
m[4][2]=b3[1];
m[5][2]=b3[3];
m[6][2]=b3[5];
//Рисуем картинку
//столбец1
Form1->Label6->Caption=m[0][0];
Form1->Label9->Caption=m[1][0];
Form1->Label12->Caption=m[2][0];
Form1->Label15->Caption=m[3][0];
Form1->Label18->Caption=m[4][0];
Form1->Label21->Caption=m[5][0];
Form1->Label24->Caption=m[6][0];
//столбец2
Form1->Label4->Caption=m[0][1];
Form1->Label7->Caption=m[1][1];
Form1->Label10->Caption=m[2][1];
Form1->Label13->Caption=m[3][1];
Form1->Label16->Caption=m[4][1];
Form1->Label19->Caption=m[5][1];
Form1->Label22->Caption=m[6][1];
//столбец3
Form1->Label5->Caption=m[0][2];
Form1->Label8->Caption=m[1][2];
Form1->Label11->Caption=m[2][2];
Form1->Label14->Caption=m[3][2];
Form1->Label17->Caption=m[4][2];
Form1->Label20->Caption=m[5][2];
Form1->Label23->Caption=m[6][2];
//Cумма каждого столбца равна:
for(int i=0;i<c;i++)   {sc[i]=0;}
for(int j=0;j<c;j++)
for(int i=0;i<r;i++){sc[j]+=m[i][j];}
Form1->Label27->Caption=sc[0];
Form1->Label25->Caption=sc[1];
Form1->Label26->Caption=sc[2];
// Вычислим среднюю сумму элементов каждого столбца
average=sum/c;
Form1->Label28->Caption=FormatFloat("0.00",average);
//Вычислим отклонение суммы каждого столбца
//      от средней суммы
for(int i=0;i<c;i++){e[i]=0;}
for(int i=0;i<c;i++){e[i]=sc[i]-average;}
Form1->Label31->Caption=FormatFloat("0.00",e[0]);
Form1->Label29->Caption=FormatFloat("0.00",e[1]);
Form1->Label30->Caption=FormatFloat("0.00",e[2]);
}

Добавлено через 10 минут и 18 секунд:
Вот результат:
Размещение элементов:

   42,8   41,4   43,7
   43,6   42,5   43,5
   42,8   42,4   42,2
   40,2   42,8   42,2
   43,5   44,3   43,3
   43,3   44,6   42,9
   44   42,3   42,4

   Сумма:
300,2   300,3   300,2

   Среднее значение:
      300,23

   Отклонение:
-0,03     0,07     -0,03


Добавлено через 4 минуты и 26 секунд:
Вот еще
Размещение элементов:

21   14   7
19   12   5
17   10   3
15   8   1
16   9   2
18   11   4
20   13   6

Сумма:
126   77   28

Среднее значение:
77,00

Отклонение:
49,00   0,00     -49,00

Добавлено через 17 минут и 55 секунд:
В последнем варианте практически никаких полезных действий не выполнилось. Как можно решить проблемму. Или можно решить другим путем и как?

[Вад]

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

Непонятно также, что должно происходить, если среднее недостижимо (т.е., если неизбежны отклонения) - каков критерий "минимальности"? Максимальное отклонение по столбцу должно быть минимизировано? Или как?

[voron]

Алгоритм решения такой:
1. Заполняю двумерный массив m[r][c]
2. Считаю сумму элементов - всех
3. Считаю сумму каждого столбца
4. Считаю среднее
5. Нахожу отклонение суммы столбца от среднего
По отклонению можно заметить и выделить макс и мин сумму стб. Затем между макс и мин столбцом пытаюсь найти пару элементов для замены - это делает массив mr1[r][r].
6. Определяю мин и макс стб.
**************************
7.Вычисляется критерий поиска k=-min-int(min) отделим десятые от целого. К сожалению другого не придумал. Может быть это и есть то место которое приводит к неправильному решению.

8. При условии пока к!=0 выполняю поиск в массиве mr1 положительной не более к разности и если нахожу меняю соответствующие эл-ты местами и если отклонение отлично от нуля прыгаю в начало и все заново считаю надеясь
что отклонение уменьшилось (как 1 проход, 2 проход итд)

Код: (C++)

for(int i=0;i<r;i++)//и минимального стб
for(int j=0;j<r;j++)
{
mr1[j][i]=m[i][ima]-m[j][imi];//здесь все возможные варианты разностей
                                        //элементов
if(mr1[j][i]>0&&mr1[j][i]<=k)//ищем соответствие для перестановки
{
double temp=0;
temp=m[i][ima];
m[i][ima]=m[j][imi];
m[j][imi]=temp;
if((e[0]!=0)&&(e[1]!=0)&&(e[2]!=0))
{goto label1;}//если уверждение верно значит считаем заново
}
}

*****************************************************
9. Если счетчик считает до 50 значит бесконечность (решения нет) или близкий к решению результат - метка 2 выводит что получилось и конец.

Добавлено через 1 час, 25 минут и 1 секунду:
Отклонение не должно быть больше чем 0.1. Если решить нельзя то максимально приблизиться. Хотябы два столбца должны быть равны среднему.

[Dimka]

К сожалению другого не придумал.

Потому что грамотная постановка задачи - это половина решения.

Сколь я понимаю, задача типовая на минимакс - минимизировать максимальное отклонение от среднего по столбцам. Алгоритмов масса, но ты их не знаешь, да и в общем-то не так уж интересно писать чужие алгоритмы - гораздо интереснее сконструировать собственный.

В связи с этой целью возникает ряд вопросов о том, насколько решение этой цели соответствует:

По отклонению можно заметить и выделить макс и мин сумму стб.

1) Почему ты выделяешь значения отклонений, а не их модули?

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

2) При помощи какого алгоритма ты их ишешь? (Словами, не кодом.)

P.S. Обрати внимание, что в минимаксной формулировке нет требования равенства - тем самым расширяется класс исходных данных. Из этой же формулировки вытекает разумный критерий наилучшего решения - когда никакие другие действия не приводят к снижению минимума.

Если всё же нужно строгое равенство, то решив задачу на минимакс и посмотрев на получивший минимум можно точно сказать: если он 0 - решение есть, если он не ноль - решения не существует.

[voron]

Это свежая мысль. О минимаксе даже не подумал. Я думал что эта задача ближе к задаче о ранце - но применить ее не получилось

1) По знаку отклонения можно определить всеже какой столбец больше среднего а какой меньше. Как поступить если будут два макс стб?

2)Допустим есть макс стб  0 и мин 2  в массиве m[7][2]. Тогда я создаю новый массив  mr1[7][7] в котором номер столбца совпадает с номером, элемента, максимального столбца массиваи m[7][0] (строки) из, которого, вычли все значения минимального стб массива m[7][2]. Т.е. в mr1 строка это индекс элемента в мин стб, а стб это индекс элемента в максс стб. Я перебирал элементы mr1[7][7] и сравнивал их с k=-min-int(min). Элемент должен быть положительным и равным либо меньшим к.

Я поищу материалы по минимакс. Это нада поставить задачу

[Dimka]

Как поступить если будут два макс стб?

А какая разница?

Прежде, чем считать или не считать это проблемой, нужно иметь представление, что с этим делать.

2) Твои сокращения слов и пристрастие к массивам понятности не добавляют.

Для любых двух столбцов любой обмен двух их элементов из них местами (например, a и b) может сопровождается изменением сумм столбцов. Если a=b, суммы столбцов не меняются; в противном случае в столбце, в котором было a и стало b, сумма изменится на +b-a, а в столбце, в котором было b и стало a, сумма изменится на +a-b.

Самое интересное здесь - отсутствие гарантии единственности минимума (т.е. могут быть локальные минимумы).

Если единственность минимума не доказана, то остаётся полный перебор. Но для массива размером X*Y, где X - количество столбцов, количество вариантов будет X^2*Y^2 (сочетание каждого столбца с каждым на сочетание каждого элемента с каждым в двух столбцах). В твоём случае 7^2*3^2=147. Жить можно. А может я и ошибаюсь - может X!*Y^2, но в любом случае не хуже (X*Y)!.

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

Тогда на всяком шаге из всего множества обменов допустимыми остаются лишь те, которые не больше текущего минимального максимума. Из них можно выбрать тот обмен, который сильнее всего понижает минимум максимума. Если остаются только такие обмены, которые сохраняют текущий уровень минимального максимума, их нужно перебирать все и запоминать уже выполненные, чтобы исключать из перебора ранее пройденные. Если в процессе перебора появился новый минимум - выбрать его. Если в процессе перебора нерассмотренных обменов не осталось - найден глобальный минимум максимума, что является основанием закончить алгоритм.

[voron]

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

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

Я делал перебор в специальный массив размерностью 7х7 и в нем старался найти положительное отклонение между элементами. т.е. если

mr1[i,j]=0 - значит одинаковы - и пропускаем
mr1[i,j]>0 - нужно сравнить с чемто например с отклонением по модулю минимального столбца. Если меньше то подходит и меняемся местами. Если больше пропускаем.
mr1[i,j]<0 - значит элемент в минимальном столбце больше чем в максимальном и если поменять отклонение минимального столбца станет еще больше (-), и соответственно макс (+) тоже больше.
                    не подходит и пропускаем.

Должна быть какае то зона нечувствительности - т.е. не жесткое равенство т.к. такого как отклонение значения может и не быть - тогда его нужно собрать несколькими заменами по чучуть.
Только как выразить эти состояния?

Может собрать все элементы в одном месте. Выполнить сортировку пузырьком, а затем разложить их по строкам в массив. Это поможет навести какойто порядок и можна будет незнаю что дальше зделать. Но будет известно где большие и где меньшие элементы

[Dimka]

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

Ничего подобного. Решением может быть хитрая комбинация, затрагивающая много столбцов сразу. Если нет - докажи.

[voron]

Вот второй пример. Там два отклонения -49 и +49.
Размещение элементов:

21   14   7
19   12   5
17   10   3
15   8   1
16   9   2
18   11   4
20   13   6
Сумма:
126   77   28
Среднее значение:
77,00
Отклонение:
49,00   0,00     -49,00

если 4 и 18 поменять местами то тогда отклонения приблизятся к нулю но этого недостаточно

Добавлено через 1 минуту и 21 секунду:
Насчет хитрой комбинации согласен. Наверно в ней и вся соль

Добавлено через 10 минут и 9 секунд:
Вот пример 3
Размещение элементов:

1.1   1.1   1
1   1   1
1   1   1
0.1   0.1   1
0.1   1   1
1   1   1
1.1   1   1

Сумма:

5.4   6.2   7

Среднее значение:

6.20

Отклонение:

-0.80   0.00   0.80

Для человека несложно все уравновесить. Но научить программу сложнее. Уверен нужно искать комбинацию. Отклонение 0.8 но такого элемента нет. В результате пользователю вернулось то что получилось.

Добавлено через 53 минуты и 50 секунд:
Попробую доказать.
Пускай имеется набор из 21 элемента. Необходимо из него составить три набора по 7 элементов при условии что сумма каждого набора должна быть равна сумме всех (21) элементов деленных на три. Изменять элементы нельзя.

Доказательство
отсортируем элементы так, чтобы a1<=a2<=a3<=....<=a(n-1)<=a(n) и составим наборы

1) a1<a4<a7<a10<a13<a16<a19
     ^   ^    ^     ^       ^    ^      ^
2) a2<a5<a8<a11<a14<a17<a20
     ^   ^     ^    ^       ^     ^     ^
3) a3<a6<a9<a12<a15<a18<a21

Пускай s - сумма всех 21 элементов. Тогда av = s/3 - требуемая сумма каждого набора.

 Сумма каждого набора будет равна соответственно s1, s2 ,s3.

 Чтобы определить насколько сумма каждого столбца отличается от требуемой посчитаем отклонение:

e1=s1-av, e2=s2-av, e3=s3-av.

Тогда возможны три случая

1) e(i)>0 значит s(i)>av

2) e(i)<0 значит s(i)<av

3) e(i)=0 значит s(i)=av - не трогаем

Находим min и max



Добавлено через 18 минут и 21 секунду:
min=e1, (mi=1); если min>e2, min=e2 (mi=2); если min>e3, min=e3 (mi=3); mi - номер набора который имеет сумму меньше требуемой

max=e1, (mа=1); если max<e2, max=e2 (mа=2); если max<e3, max=e3 (mа=3); mа - номер набора который имеет сумму больше требуемой

Далее необходимо найти критерий поиска


Добавлено через 17 минут и 48 секунд:
Теперь имеет значение какое а(i):

если а(i) - вещественное то к=|min|-int|min|; к - критерий поиска

если а(i) - целое то к=|min|;

Строим таблицу разностей элементов между ma и mi наборами



Добавлено через 29 минут и 54 секунды:
rj(i)=ma(aj)-mi(aj), 1<i<7, 1<j<7;

если r=k значит ma(aj) больше mi(aj) на k. Значит ma набор станет меньше на к, а mi набор станет больше на к после того как поменять местами a(i) и a(j)

[Dimka]

Что-то это не похоже на доказательство. И доказательство чего именно? У тебя получился алгоритм, а доказывать можно только при помощи логических утверждений. Допустим, на системе предикатов первого порядка. Например, по пред- и постусловиям.

Но даже если не доказывать. Наверно, ты знаешь алгоритм ханойской башни? Нет ли аналогий с твоим случаем?

1) Сначала предполагаешь, что решение можно получить обменами, каждый из которых понижаем минимум максимума. Пробуешь получить решение.
2) Если решение не получается, ишешь такой обмен, который увеличивает исходный минимум минимально возможным образом, и затем повторяешь шаг 1. Если опять решение не получилось, ищешь следующий повышающий минимум обмен и опять шаг 1. И так, пока не найдёшь комбинацию или не переберёшь все варианты.

Разумеется, это не оптимальный алгоритм для твоей задачи, но зато простой для понимания. А вот можно ли на его основе построить доказательство? И, кстати, можно ли утверждать, что предварительная сортировка даёт максимальное отклонение минимума от нуля?

[voron]

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

[Dimka]

Предварительная сортировка дает определенность например первые элементы набора меньше последних.

А зачем тебе это? Ты уже придумал, что с этим делать?

и это не оптимальный алгоритм

Наверно сначала нужно решить задачу в принципе, и только потом думать об оптимальности.

Задача о ранце намного ближе.

Придётся-таки сказать, что это заблуждение - надеялся, что сам догадаешься. Ты можешь решить задачу о ранце для одного столбца, но столбцов у тебя много, поэтому решая эту задачу для одного, ты портишь решение для других, и это принципиально неустранимый момент, если использовать подход "задачи о ранце". Твоя задача - качественно другая, несмотря на похожесть формулировки.

[voron]

Спасибо! Буду решать

[Dimka]

Вернее, можно решать задачу о ранце, но лишь как подзадачу.

1) Получить ВСЕ решения для одного столбца.
2) Взять одно решение для первого столбца, исключить его элементы из общего множества и решать задачу для второго столбца. Переход от второго столбца к третьему и далее аналогичен.
3) Если для какого-то столбца задача не решается, вернуться к предыдущему столбцу, взять следующее его решение и опять пробовать. Если у предыдущего столбца не осталось нерассмотренных решений, возвращаться к ещё более раннему столбцу. Наконец, если все решения первого столбца перебраны, а решения не найдено - его нету.

По-моему, это не сильно отличается от того, что я написал выше, если единицей решения рассматривать не столбец, а отдельный обмен значениями.

[voron]

Проще так как уже работает. Только определится с критерием на основании которого выполнить перестановку. Я считаю что в алгоритме есть ошибка; научится запоминать сделанное, чтобы не возвращалось все обратно (не инвертировалось)

Добавлено через 1 час, 48 минут и 15 секунд:
Моя программа работает так: находит мин и макс столбци. Берет мин отклонение и ищет такую разность между элементами  макс и мин столбцов чтобы чтобы эта разность была  в диапазоне  0<r<|отклонение мин|  т.е. элелемент макс столбца все же больше элемента мин столбца. Отклонение постоянно меняется после перестановок. Но оно может как расти так и убывать. Если оно станет убывать это то что требуется. Но если станет расти тогда это условие не работает (получается как во тором примере 1 и 3 столбец поменялись местами). Нужен какой то регулятор

Добавлено через 18 дней, 12 часов, 50 минут и 16 секунд:

Вернее, можно решать задачу о ранце, но лишь как подзадачу.

1) Получить ВСЕ решения для одного столбца.
2) Взять одно решение для первого столбца, исключить его элементы из общего множества и решать задачу для второго столбца. Переход от второго столбца к третьему и далее аналогичен.
3) Если для какого-то столбца задача не решается, вернуться к предыдущему столбцу, взять следующее его решение и опять пробовать. Если у предыдущего столбца не осталось нерассмотренных решений, возвращаться к ещё более раннему столбцу. Наконец, если все решения первого столбца перебраны, а решения не найдено - его нету.

По-моему, это не сильно отличается от того, что я написал выше, если единицей решения рассматривать не столбец, а отдельный обмен значениями.

   Как вариант - посчитать среднеквадратичное отклонение  сумм столбцов.
Тогда можно перебирать варианты не вслепую.
 Например попробовали переставить местами элементы 1 го и 2 го столбца посчитали среднеквадратичное отклонение и сравнили со среднеквадратичным отклонением, которое было до этого.
 Если отклонение уменьшилось так и оставить - пробовать следующие варианты.
 Если увеличилось вернуть как было, пропустить этот вариант и пробовать следующий.

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

[Dimka]

voron, а зачем среднеквадратичное отклонение? Достаточно просуммировать модули всех отклонений - это и считать проще.

[voron]

Dimka, огромное спасибо!
 
Похоже, что это работает  
Написал небольшую консольную программку котора демонстрирует данный метод.

Может быть еще придется поработать напильником но затея хорошая.
Код выложу попозже после форматирования  

Добавлено через 1 час, 45 минут и 36 секунд:

Код: (C++)

#include <cstdlib>
#include <iostream>
#include <math.h>
using namespace std;

const int r=7;
const int c=3;
double m[r][c]={0};
double copym[r][c]={0};
double sum=0, s1=0,s2=0,s3=0,old=0,current=0;
double av=0,temp=0,e1=0,e2=0,e3=0;
double ss1=0,ss2=0,ss3=0;
int counter=0;
int main()
{
m[0][0]=1;
m[1][0]=2;
m[2][0]=3;
m[3][0]=4;
m[4][0]=5;
m[5][0]=6;
m[6][0]=7;

m[0][1]=8;
m[1][1]=9;
m[2][1]=10;
m[3][1]=11;
m[4][1]=12;
m[5][1]=13;
m[6][1]=14;

m[0][2]=15;
m[1][2]=16;
m[2][2]=17;
m[3][2]=18;
m[4][2]=19;
m[5][2]=20;
m[6][2]=21;
//Выводим матрицу элементов
   cout<<"\n\n\t The program beginning\n\n";
   cout<<"\n\n\t Initial matrix of elements\n\n";
    for(int row=0;row<r;row++)
    {
       copym[row][0]=m[row][0];
        copym[row][1]=m[row][1];
         copym[row][2]=m[row][2];
         
            cout<<"\t"<<m[row][0]<<"\t"<<m[row][1]<<"\t"<<m[row][2]<<"\t"<<endl;
           
    }
    cout<<endl;
//---------------------------------------------------------------------
  //сумма каждого столбца
  cout<<"We count the sum of every column \n";
  s1=s2=s3=0;
    for(int row=0;row<r;row++)
    {
    s1+=m[row][0];
    s2+=m[row][1];
    s3+=m[row][2];    
    }
 cout<<"\n\nSum of every column:\n\n\t"<<s1<<"\t"<<s2<<"\t"<<s3<<"\t\n\n";  
//---------------------------------------------------------------------  
 //средняя сумма
 for(int col=0;col<c;col++)
    for(int row=0;row<r;row++)
    {
    sum+=m[row][col];
    }

  av=0;
  av=sum/3;
  cout<<"\n Middle sum of column = "<<av<<endl<<endl;
//---------------------------------------------------------------------  
//отклонение
e1=e2=e3=0;
e1=s1-av;    
e2=s2-av;
e3=s3-av;
cout<<"\n\nDeviation of sum of column from a middle sum:\n\n\t"<<e1<<"\t"<<e2<<"\t"<<e3<<"\t\n\n";  
//----------------------------------------------------------------------
//сумма модулей отклонений
current=0;
current=fabs(e1)+fabs(e2)+fabs(e3);
cout<<"\n The sum of modules of all deviations \n\n\t\t"<<current<<endl<<endl;
//---------------------------------------------------------------------  
//принимаем Current как old
old=current;

//---------------------------------------------------------------------<<<<<<<<<<<<
//do
//{

for(int c1=0;c1<c;c1++)

for(int r1=0;r1<r;r1++)
for(int c2=0;c2<c;c2++)
for(int r2=0;r2<r;r2++)
{
//-----------------------------------------------------------------------
if(old<0.1)
{
           break;
}
//-----------------------------------------------------------------------
if(c2==c1)
{

c2++;

cout<<"\n\n >>C2++<<\n\n";
}
//-----------------------------------------------------------------------
cout<<"\n\n*****COUNTER="<<counter<<"*****\n\n";
 temp=0;
 temp=m[r1][c1];
 m[r1][c1]=m[r2][c2];
 m[r2][c2]=temp;
//*********************************************************************
//Выводим матрицу элементов
   cout<<"\n\n\t The changed matrix of elements \n\n";
   
    for(int row=0;row<r;row++)
    {
           
            cout<<"\t"<<m[row][0]<<"\t"<<m[row][1]<<"\t"<<m[row][2]<<"\t"<<endl;
           
    }
    cout<<endl;
//---------------------------------------------------------------------
  //Сумма каждого столбца
  cout<<"We count the sum of every column \n";
  s1=s2=s3=0;
    for(int row=0;row<r;row++)
    {
    s1+=m[row][0];
    s2+=m[row][1];
    s3+=m[row][2];    
    }
 cout<<"\n\nSum of every column:\n\n\t"<<s1<<"\t"<<s2<<"\t"<<s3<<"\t\n\n";  

//---------------------------------------------------------------------  
//Отклонение
e1=e2=e3=0;
e1=s1-av;    
e2=s2-av;
e3=s3-av;
cout<<"\n\nDeviation of sum of column from a middle sum:\n\n\t"<<e1<<"\t"<<e2<<"\t"<<e3<<"\t\n\n";  
//----------------------------------------------------------------------
//Сумма модулей отклонений
current=0;
current=fabs(e1)+fabs(e2)+fabs(e3);
cout<<"\n The sum of modules of all deviations \n\n\t\t"<<current<<endl<<endl;
//---------------------------------------------------------------------  
//*********************************************************************
if(current<old)
{

old=current;
cout<<"\n\n >>>>>FIND JAMP NEXT>>>>>\n\n";
}

if(current>old)
{
temp=0;
 temp= m[r1][c1];
 m[r1][c1]=m[r2][c2];
 m[r2][c2]=temp;

cout<<"\n\n <<<<<<RETURN AND JAMP NEXT>>>>>\n\n";
}

if(current==old)
{

 cout<<"\n\n >>>>>JAMP NEXT>>>>>\n\n";
}

counter++;
}                                                                      
//}while(old>0.1);
//---------------------------------------------------------------------<<<<<<<<<<<
//Выводим результат
   cout<<"\n\n\t\t\t Result of work of the program\n\n";
   cout<<"\n\n\tInitial matrix of elements\t\tThe sorted matrix of elements\n\n";
    for(int row=0;row<r;row++)
    {
             
            cout<<"\t"<<copym[row][0]<<"\t"<<copym[row][1]<<"\t"<<copym[row][2]<<"\t\t\t"
            <<m[row][0]<<"\t"<<m[row][1]<<"\t"<<m[row][2]<<endl;
           
    }
    cout<<endl;
//---------------------------------------------------------------------
//---------------------------------------------------------------------
  //сумма каждого столбца
 
  s1=s2=s3=ss1=ss2=ss3=0;
    for(int row=0;row<r;row++)
    {
    s1+=m[row][0];
    ss1+=copym[row][0];
    s2+=m[row][1];
    ss2+=copym[row][1];
    s3+=m[row][2];
    ss3+=copym[row][2];  
    }
 cout<<"\n\n\t\t\tTheir sum of columns is equal:\n\n\t"<<ss1<<"\t"<<ss2<<"\t"<<ss3<<
                        "\t\t\t"<<s1<<"\t"<<s2<<"\t"<<s3<<"\n\n";  
//---------------------------------------------------------------------  
    system("PAUSE");
    return EXIT_SUCCESS;
}
 

[Dimka]

Ну я решил попробовать вариант с одиночными перестановками. За пару часиков вышло следующее:

Код: (C)

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define N 3
#define M 7

typedef int matrix[N][M];
typedef int error[N];

void initialize(matrix m) {
  int i, j;
  for(i = 0; i < N; ++i)
    for(j = 0; j < M; ++j)
      m[i][j] = rand() % (M * N);
}

void display(matrix m, error e) {
  int i, j;
  for(i = 0; i < N; ++i) {
    for(j = 0; j < M; ++j)
      printf("%2u ", m[i][j]);
    printf(": %i\n", e[i]);
  }
}

void calc_error(matrix m, error e, int *te) {
  int i, j, ae = 0;
  for(i = 0; i < N; ++i) {
    e[i] = 0;
    for(j = 0; j < M; ++j)
      e[i] += m[i][j];
    ae += e[i];
  }
  ae /= N;
  *te = 0;
  for(i = 0; i < N; ++i) {
    e[i] -= ae;
    *te += abs(e[i]);
  }
}

int exchange(int a, int b, matrix m, error e) {
  int ea, eb, i, j, nea, neb, bea, beb, k, l, x;
  ea = abs(e[a]);
  eb = abs(e[b]);
  if(abs(e[a] + e[b]) < ea + eb) {
    bea = ea;
    beb = eb;
    k = -1;
    l = -1;
    for(i = 0; i < M; ++i)
      for(j = 0; j < M; ++j) {
        nea = abs(e[a] - m[a][i] + m[b][j]);
        neb = abs(e[b] - m[b][j] + m[a][i]);
        if(nea < bea && neb < beb) {
          bea = nea;
          beb = neb;
          k = i;
          l = j;
        }
      }
    if(k != -1 && l != -1) {
      e[a] = e[a] - m[a][k] + m[b][l];
      e[b] = e[b] - m[b][l] + m[a][k];
      x = m[a][k];
      m[a][k] = m[b][l];
      m[b][l] = x;
      return 1;
    }
  }
  return 0;
}

void solve(matrix m) {
  error es;
  int i, j, x = 1, e;
  calc_error(m, es, &e);
  while(e > 0 && x == 1) {
    x = 0;
    for(i = 0; i < N; ++i)
      for(j = i + 1; j < N; ++j)
        if(exchange(i, j, m, es))
          x = 1;
    calc_error(m, es, &e);
  };
}

int main() {
  matrix m;
  error e;
  int te;
  srand((unsigned int)time(NULL));
  initialize(m);
  printf("\tInitial matrix\n");
  calc_error(m, e, &te);
  display(m, e);
  printf("\tError is %i\n\n", te);
  solve(m);
  printf("\tFinal matrix\n");
  calc_error(m, e, &te);
  display(m, e);
  printf("\tError is %i\n", te);
  if(te == 0)
    printf("\tSolution was found.\n");
  else
    printf("\tSolution was not found.\n");
}

Принцип работы. Инициализация - случайными числами. Далее крутится цикл до тех пор, пока суммарная ошибка не станет равна 0 или нельзя будет сделать ни одной перестановки. Внутри цикла перебираются все сочетания столбцов. Для каждого сочетания столбцов ищется наилучшая перестановка, максимально сокращающая ошибки в обоих столбцах. Если перестановка произошла, этот факт запоминается.

[voron]

 Получается так, что вариант с одиночными перестановками работает еще быстрее и еще  самый точный из тех что здесь представленны  .
 Использование функций добавляет универсальности, чего у меня не получилось из-за того, что я так и не понял как передать в функцию двухмерный массив  .
 Физический смысл этой задачи заключается в том чтобы оптимально разместить набор молотков в дробилках среднего 7х3 и крупного дробления 4х10 допустимая погрешность чтобы оборудование не вышло из строя 100гр. До этого все делалось на бумаге.
 Но программа уже оформлена. Если моя версия запартачит то будет еще одна версия  .

Спасибо за помощь!

[Dimka]

voron, я проверял размеры до 25х20.

Однако моё решение исходит из предположения, что на пути к оптимальному решению ошибка монотонно убывает. А это не доказано.

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

[voron]

Да, Dimka вполне! Мой вариант заработал и на 40 молотков, правда с небольшого пинка. Одна секунда и решение есть! Дольше вбивать все эти числа.

[Dimka]

Вообще у меня есть одно условие:

Код:

if(abs(e[a] + e[b]) < ea + eb)

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

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

Однако такой подход в частности даёт решения, у которых суммарная ошибка концентрируется в каком-нибудь одном столбце. Т.е. мой алгоритм не стремится как можно равномернее "размазать" неустранимую ошибку по столбцам.

Наверно это стоит иметь в виду.

[voron]

Да, в этом есть изюминка. Встречаются такие случаи и например если в матрице 4х10 в двух столбцах может быть отклонение положительное и в двух отрицательное то при сравнении элементов в таких парах столбцов ни к чему не приведет . Довольно таки разумно исключать бесполезные варианты. Я вот тест проводил своей программки и довольно часто встречаются случаи, когда приходится нажать кнопку несколько раз и комбинация при этом меняется и отклонение стремится к 0. Иногда при повторном нажатии кнопки ничего не происходит. Вот я и подумал хорошо бы кнопку саму по себе сделать так, чтобы она нажималась пока решения не будет. Но это тоже трата времени. Проще будет уже делать на вашей основе 

Добавлено через 17 часов, 24 минуты и 12 секунд:
Испытания на пользователе прошли успешно. Работает точно и данные не портит. Пожалуй пускай остается старый вариант.
Еще раз спасибо за помощь!