поиск минимальной суммы произведений, Чистый С Опции

[PAS_Dil]

Доброго времени суток.
Поставили перед мною следующую задачу и наказили выполнить на С.
Данны 2 массива длины n. Можно брать по одному члену из каждого м перемножать их. Напистаь программу печатающую пары номеров массивов так, чтобы сумма их произведений была минимальной. Каждый член массива может использоваться лишь однажды.

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

Благодарю за внимание.

[Michael_Rybak]

Условие такое. Даны два набора чисел, по n в каждом. К примеру:

1) 2 5 1
2) 3 3 1

Мы можем расположить числа в произвольном порядке, например:

1) 1 2 5
2) 3 3 1

или

1) 5 2 1
2) 3 1 3

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


1) 5 1 2
2) 1 3 3

5*1 + 1*3 + 2*3 = 14

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

Решение: нужно просто отсортировать оба массива. В нашем случае:

1) 1 2 5
2) 1 3 3

1*1 + 2*3 + 5*3 = 22

Чтобы доказать, что это правильно, покажем, что, сортируя, мы улучшаем результат. Пусть на некотором месте в верхней строке стоит число А, в нижней строке - а, а на другом месте, в верхней строке стоит В, в нижней - в. Имеем: Aa+Bb. Легко убедиться, что множить наоборот, т.е. Ab+Ba, будет выгоднее только тогда, когда порядок чисел A,B и a,b - разный, т.е. когда (A-B)(a-b)<0 - это получается непосредственно из предположения, что Ab+Ba>Aa+Bb. Применяя это рассуждение много раз, получим что-то вроде пузырьковой сортировки

[Гость]

Огромное спасибо я вот написал что то вроди этого, но возникала пробелма -как мне вывести индексы - мне на выход нужно передать индексы этих пар в старом массиве - не отсортированном. Т.е. я должен не только отсортировать массив но ещё и хранить индекс каждого элемента в массиве до его сортировки, чтобы на выходе можно было увидеть что мол элемент 2 * элемент 4 + элемент 6 * 7 элэмент....
Вот прошу помочь

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

#define MAX 3
#define OBNUL 0

main ()
{
	int i;
	int mas1[MAX] = {12,2,4};   // массив 1
	int mas2[MAX] = {8,42,34}; // массив 2
	int m1_t[MAX];
	int m2_t[MAX];
	int obn, nbl;	   // переменная счётчик
	int min, max, vrem; 
	obn = OBNUL; nbl = OBNUL; min = OBNUL; max = OBNUL; vrem = OBNUL;
	min = mas1[1];

	for(obn = OBNUL, i=0; obn < MAX; obn++, i++)
		{
			min = mas1[obn];
			for (nbl = OBNUL; nbl < MAX; nbl++)	
				{
					if (mas1[nbl] > min)
					{
						m1_t[i] = obn;
						vrem = mas1[nbl];
						mas1[nbl] = min;
						mas1[obn] = vrem;
						break;
					} 							
				}
		}

	
	for(obn = OBNUL; obn < MAX; obn++)
		{
			for (nbl = OBNUL; nbl < MAX; nbl++)	
				{
					if (mas2[nbl] < mas2[obn])
					{
						vrem = mas2[nbl];
						mas2[nbl] = mas2[obn];
						mas2[obn] = vrem;
						break;
					} 							
				}
		}
	for(obn = OBNUL; obn < MAX; obn++)
		printf("%d\n", mas1[obn]);
	printf("----------\n");
	for(obn = OBNUL; obn < MAX; obn++)
		printf("%d\n", mas2[obn]);
	printf("----------\n");
	

[volvo]

я должен не только отсортировать массив но ещё и хранить индекс каждого элемента в массиве до его сортировки

#include <stdio.h>

#define MAX 3
#define OBNUL 0

void swap(int *a, int *b) {
  int T;
  T = *a; *a = *b; *b = T;
}

main ()
{
	int i, j;
	int mas1[MAX] = {12,2,4};
	int mas2[MAX] = {8,42,34};

	int ix_1[MAX] = {1, 2, 3},
		ix_2[MAX] = {1, 2, 3};

	int obn = OBNUL;

	for(i = 0; i < MAX; ++i)
	  for(j = MAX - 1; j >= i + 1; --j) {
		if(mas1[j - 1] > mas1[j]) {
		  swap(&mas1[j - 1], &mas1[j]);
		  swap(&ix_1[j - 1], &ix_1[j]);
		}

		if(mas2[j - 1] > mas2[j]) {
		  swap(&mas2[j - 1], &mas2[j]);
		  swap(&ix_2[j - 1], &ix_2[j]);
		}
	  }

	for(obn = OBNUL; obn < MAX; obn++)
		printf("%d(%d) ", mas1[obn], ix_1[obn]);
	printf("\n----------\n");
	for(obn = OBNUL; obn < MAX; obn++)
		printf("%d(%d) ", mas2[obn], ix_1[obn]);
	printf("\n----------\n");

	return 0;

}

Идея понятна?