Наибольшая сумма из n элементов в множестве k

У нас есть значение maxSum (лимит суммы), есть массив значений integer, и число n (то есть из скольки элементов нужно составить сумму из элементов массива).
Нам нужно найти элементы массива, которые дают максимально возможную сумму из n элементов данного массива, которая будет <= (меньше или равна) лимиту (один элемент массива нельзя брать больше 1 раза)
Возможно, задача на динамическое программирование.
Помогите придумать алгоритм работы.
Просто сделать перебор всех значений, и смотреть где сумма максимальная, как вы понимаете, очень затратно по времени и памяти. Как сделать проще?

Например, массив: [1, 4, 2, 5, 8], лимит: 7, n = 2, ответ: [2, 5], n = 3, ответ: [1, 4, 2]. Если не возможно составить, вывести -1.

0

Сообщение от Radmir2015 Возможно, задача на динамическое программирование.

Действительно похоже на динамику.
Пускай dp[x][y][z] = ответ на нашу задачу, если мы используем x первых элементов массива, лимит равен y, а количество элементов которое хотим взять из массива z.
Тогда у нас есть 2 варианта.
1) Либо мы берем число с номером х и тогда формула такая
arr[x] + dp[x - 1][y - arr[x]][z - 1]
arr[x] число из массива которое прибавляем потому что мы его взяли, x - 1 почему берем очевидно, y - arr[x] потому что лимит был y, но мы взяли число arr[x] и теперь он уменьшится, z - 1 количество элементов которые мы можем взять из массива тоже на 1 очевидно уменьшается.
2) Мы не берем число с номером х тогда формула такая
dp[x - 1][y][z]
Лимит y как был так и остался, z тоже без изменений.
Итоговая формула dp[x][y][z] = max(arr[x] + dp[x - 1][y - arr[x]][z - 1], dp[x - 1][y][z])
Когда x = 0 или y = 0 или z = 0, то dp[x][y][z] = 0.
Когда z > x ответ тоже 0.
З.Ы Пишу ночью, потому может что-то не учел, а может совсем бред написал, формулы не проверял, потому что времени сейчас нет. Если кто поправит формулы буду рад.

0

Сообщение от Radmir2015 Возможно, задача на динамическое программирование

Еще сомневаешься? Задача о рюкзаке в чистом виде

0