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

[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. Применяя это рассуждение много раз, получим что-то вроде пузырьковой сортировки