Задачка на логику для программистов

Т1000, 440 просмотров

Имеется в кластере 4 компа и дано новых 5 модулей оперативки, которые необходимо распределить между компьютерами. Причём распределить модули памяти нужно таким образом, чтобы сумма прироста производительностей кластера была максимальной.
Коэффициенты прироста производительности каждого компьютера при оснащении его модулями памяти:
количество | прирост произодительности
модулей памяти | комп1 | комп2 | комп3 | комп4
1 | 0.1 | 0.12 | 0.16 | 0.07
2 | 0.12 | 0.15 | 0.19 | 0.11
3 | 0.15 | 0.19 | 0.23 | 0.18
4 | 0.2 | 0.27 | 0.25 | 0.20
5 | 0.25 | 0.31 | 0.29 | 0.30
Общий прирост производительности считать как сумму приростов производительности для каждого компьютера.
Какой алгоритм для решения данной задачи вы бы выбрали в качестве самого оптимального/интересного решения?

Примечание:
Jesterok,
а для оптимального решения данной задачи в виде программы как симплекс-метод здесь поможет?

Примечание:
Jesterok,
симплекс-метод я немного знаю. Но в данном случае даже не понимаю, как будут выглядеть ограничения и целевая функция.
P.S. Методом прямого перебора задачу я решил. Но хотелось бы узнать более умный способ.

Примечание:
Нужно методом динамического программирования.

Ответы:

klen77

ты правда думаешь, что сейчас самое время для таких задач? :)

neomichi

я вообще незнаю о чем ты =)) но знаю что есть предмет нызываемый методы оптимизации!!! вот, а там есть это класическая задача на экстремум,с ограничениями типа неравеств, и решается задачи на раз два, на курсе этак 3 , в мех-мате =)

Jesterok

Правильно делают, что отсылают к методам оптимизации. Формализуя данное условие (т.е составив мат. модель) вы придете к задаче линейного программирования, которая включает в себя целевую функцию, систему ограничений (все числа у вас уже есть в табличке), и ограничения на знак (т.к иксы здесь характеризуют прирост производительности, то все xj >= 0). Приведя данную задачу к канонической форме, можно смело обращаться к симплекс-методу [1]. Постепенно прыгая по вершинам многогранника решений мы-таки придем к оптимальному. Сам симплекс-метод не сложен. Такую небольшую задачку быстрее сделать в excel (с применением этого метода, конечно. Показательный примерчик могу выслать на мыло или залить куда-нибудь). Но если нужно в дальнейшем обрабатывать большие задачи, то конечно лучше написать программку соответствующую.

Jesterok

Дополнение #1, симплекс-методом можно решить ЛЮБУЮ задачу линейного программирования. Решив её, в строке z-оценок будет стоять сумма производительности, а значения иксов будут показывать, каким образом нужно распределить память. Думаю мои слова сейчас ничего вам особо не говорят: смотрите книги по МО, в частности симплекс-метод и структуру симплекс-таблицы (тогда поймете, что я имел ввиду под "z-оценками" :) ).
Еще вариант - метод прямого перебора [1]. Т.е последовательный перебор базисных решений и отыскание такого, при котором целевая функция будет максимальна.

wowan1

Данную задачу настоящие программисты решат как раз методом перебора в цикле:)

Александр Хегай

вот сайт поищи там было - www.TheCodeProject.com

UTF-8

Не согласен. Симплекс метод не подойдет, так как задача целочисленная. http://first.boom.ru/Products/Theory/integer.htm
Свести задачу к Задаче линейного программирования можно, например, так.

leon38

поддерживаю вован1-- перебор в цикле: мгновенно и вульгарно просто

15 лет назад

RPI.su - самая большая русскоязычная база вопросов и ответов. Наш проект был реализован как продолжение популярного сервиса otvety.google.ru, который был закрыт и удален 30 апреля 2015 года. Мы решили воскресить полезный сервис Ответы Гугл, чтобы любой человек смог публично узнать ответ на свой вопрос у интернет сообщества.

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

Чтобы связаться с нами по любому вопросу О САЙТЕ (реклама, сотрудничество, отзыв о сервисе), пишите на почту [email protected]. Только все общие вопросы размещайте на сайте, на них ответ по почте не предоставляется.