Алгоритм Вопрос Максимизировать среднее значение функций

Question

У меня есть набор из N неубывающих функций, каждая из которых обозначается F _i (h), где h - целое число. Функции имеют числовые значения.

Я пытаюсь найти способ максимизировать среднее значение всех функций с учетом некоторого общего значения H.

Например, скажем, каждая функция представляет оценку по заданию. Если я потрачу h часов на задание i, я получу оценку g = F _i (h). Мне дается H часов, чтобы закончить все задания. Я хочу получить максимальную среднюю оценку за все задания.

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

РЕДАКТИРОВАТЬ: Я думаю, что динамическое программирование может быть использовано, чтобы понять это, но я не уверен на 100%.

РЕДАКТИРОВАТЬ 2: я нашел пример в своей книге по алгоритмам, когда я учился в университете, это почти та же самая проблема посмотрите здесь на Google Books .

Answer 1

Я не знаю о программировании, но в математике функции функций называются функционалами, а подходящая математика - это вариационное исчисление.

Answer 2

Посмотрите на линейное программирование, раздел целочисленное программирование

Answer 3

У меня один вопрос: сколько у вас функций и сколько часов?

Мне кажется, что исчерпывающий поиск был бы вполне уместен, если бы ни один не был слишком высоким.

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

F1 = [0, 1, 1, 5] # ie F1[0] == 0, F1[1] == 1
F2 = [0, 2, 2, 2]

Тогда, если у меня есть 2 часа, мой лучший способ сделать это:

F1[1] + F2[1] == 3

Если у меня есть 3 часа, мне лучше:

F1[3] + F2[0] == 5

Таким образом, профиль является анархическим, учитывая количество часов, что означает, что если решение существует, оно состоит в манипулировании количеством функций.

Таким образом, мы можем ввести методы по одному:

R1 = [0, 1, 1, 5] # ie maximum achievable (for each amount) if I only have F1
R2 = [0, 2, 3, 5] # ie maximum achievable (for each amount) if I have F1 and F2

Представление новой функции занимает O(N) время, где N - общее количество часов (конечно, мне нужно было бы сохранить точное перераспределение ...)

Таким образом, если у вас есть M функций, алгоритм равен O(M*N) с точки зрения количества выполняемых функций.

Некоторые функции могут быть не тривиальными, но этот алгоритм выполняет неявное кэширование: то есть мы только один раз оцениваем данную функцию в данной точке!

Полагаю, нам было бы лучше, если бы мы могли использовать свойство increasing, но, полагаю, я не уверен насчет специфики. Жду умного парня!

Так как это домашнее задание, я воздержусь от публикации кода. Я просто хотел бы отметить, что вы можете «сохранить» перераспределение, если ваши R таблицы состоят из пар (score,nb), где nb указывает количество часов, использованных в последнем введенном методе.

Answer 4

Взгляните на Проблема ограниченного ранца и приведенный алгоритм динамического программирования.

Answer 5

Если функции в F монотонно растут в своих областях, тогда применим параметрический поиск (поиск Meggido).

Answer 6

Генетические алгоритмы иногда используются для такого рода вещей, но результат, который вы получите, не будет оптимальным, но близок к нему.
Для «настоящего» решения (я всегда чувствую, что генетика является своего рода обманом), если мы можем определить некоторые свойства функций (повышается ли функция X? Есть ли у них асимптоты, которыми мы можем злоупотреблять? какой-то механизм анализа для каждой функции, и взять его оттуда. Если у нас нет свойств ни для одного из них, они могут быть чем угодно. Моя математика не очень хорошая, но эти функции могут быть безумными факториалами ^ 99, что равно нулю, если ваш h не равен 42 или около того.
Без дополнительной информации или знания, что ваша программа может проанализировать и получить некоторую информацию. Я бы пошел генетики. (Было бы целесообразно применить к нему некоторую анализирующую функцию, и если вы найдете некоторые свойства, которые вы можете использовать, используйте их, иначе обратитесь к генетическому алгоритму)