Программирую уже несколько лет, но тут впал в ступор.
Задача в следующем:
Есть 4 массива с целочисленными значениями в каждом из которых по 1024 элемента.
Содержимое массивов выглядит примерно так:
arr1[] arr2[] arr3[] arr4[]
4 12040 4 3091
3 13393 3 3339
3 12150 3 2858
5 7035 3 2771
3 11050 3 1847
... ... ... ...
Заранее известно, что произведение соответствующих элементов первого и второго массива и произведение соответствующих элементов третьего и четвертого массива убывает с возрастанием индекса.
То есть:
arr1[0]*arr2[0] > arr1[1]*arr2[1] > arr1[2]*arr2[2] > ...
и
arr3[0]*arr4[0] > arr3[1]*arr4[1] > arr3[2]*arr4[2] > ...
Необходимо заполнить двумерный массив целочисленных значений int[256][2] result, так, чтобы он хранил индексы выбранные из пары массивов arr1, arr2 и arr3 arr4
Например:
result[0][0] = 0, result[0][1] = 0
result[1][0] = 0, result[1][1] = 1
result[2][0] = 0, result[2][1] = 2
result[3][0] = 0, result[3][1] = 4
result[4][0] = 1, result[4][1] = 3
result[5][0] = 1, result[5][1] = 5
Критерий выбора индексов следующий:
int sum = 0;
for(int i=0; i<256; ++i){
sum += arr1[result[i][0]] + arr3[result[i][1]] * arr4[result[i][1]];
}
Необходимо, чтобы переменная sum была в итоге насколько это возможно большой.
Каждый уникальный индекс соответствующий элементам из пары массивов arr3, arr4 можно указывать лишь однажды, то есть, если result[0][1] = 0, то result[x][1] уже не можт быть равен 0.
Индекс соответствующий элементам из пары массивов arr1, arr2 можно указывать неоднократно, но есть следующее ограничение:
Основываясь на приведенном примере - если result[0][0] = 0, result[0][1] = 0
Мы берем нулевой элемент массива arr2, вычитаем из него нулевой элемент массива arr4
Получаем: 12040 - 3091 = 8949
result[1][0] = 0, result[1][1] = 1
Берем нулевой элемент массива arr2, вычитаем из него первый элемент массива arr4
Получаем: 8949 - 3339 = 5610
result[2][0] = 0, result[2][1] = 2
Берем нулевой элемент массива arr2, вычитаем из него второй элемент массива arr4
Получаем: 5610 - 2858 = 2752
Теперь нулевому элементу массива arr2 уже не может соответствовать третий элемент массива arr4, так как он больше. Значит берем не третий а четвертый элемент из массива arr4.
Вобщем, если кто-нибудь осилит дочитать до этой строки, напишите хоть какие-нибудь догадки, как реализовать эту выборку, чтобы вычисления занимали не более нескольких минут.
Примечание:
>зачем это, не понятно...
Зная это, будет удобнее подбирать подходящие значения, чем если бы элементы массивов были бы раположены хаотично.
>почему 256, если в начальном 1024?
Такова задача, нужно подобрать 256 пар значений.
>здесь нет arr2?
Да, arr2 здесь не используется.
Примечание:
Спасибо за внимание. Разобрался.
RPI.su - самая большая русскоязычная база вопросов и ответов. Наш проект был реализован как продолжение популярного сервиса otvety.google.ru, который был закрыт и удален 30 апреля 2015 года. Мы решили воскресить полезный сервис Ответы Гугл, чтобы любой человек смог публично узнать ответ на свой вопрос у интернет сообщества.
Все вопросы, добавленные на сайт ответов Google, мы скопировали и сохранили здесь. Имена старых пользователей также отображены в том виде, в котором они существовали ранее. Только нужно заново пройти регистрацию, чтобы иметь возможность задавать вопросы, или отвечать другим.
Чтобы связаться с нами по любому вопросу О САЙТЕ (реклама, сотрудничество, отзыв о сервисе), пишите на почту [email protected]. Только все общие вопросы размещайте на сайте, на них ответ по почте не предоставляется.