Наиболее быстрый алгоритм получения максимальной суммы

← →
Borealis (2003-11-13 20:55) [0]

Имеем некий массив целых чисел. Массив динамический, потому он может состоять из нескольких десятков элементов, а может и из нескольких десятков тысяч. Из этого набора целых чисел нужно выбрать такой набор чисел, что бы в сумме получилось максимально возможное, для этого набора, число, но не превышающее некоторую константу К.

Какой вы предложите мне алгоритм для решения этой задачи?

Пробовал методом перебора в рекурсивных циклах, но это работает удручающе медленно, несмотря на то, что все операторы входящие в циклы я до предела оптимизировал.

Также пробовал перед началом перебора посортировать массив по возрастанию, а в процедуре прерывать цикл если текущий элемент при сложении с накопленной суммой превышает константу К - то есть следующие элементы на текущем уровне уже можно не проверять так как они заведомо будут такими же или даже большими. Но и такой, оптимизированный алгоритм ощутимого выигрыша во времени не даёт - максимальный выигрыш не превышает одного рекурсивного уровня.

← →
default © (2003-11-13 21:43) [1]

как же ты с использованием сортировки-то делал?
у тебя же условие ""максимальной суммы"
то есть, чтобы разность "K-Сумма" была минимальной
вот, к примеру, твоя отсортированная последовательность
1 2 3 4 7 8 9
K=15
начинаешь значит складывать 1+2+3+4=10=S1
(на 7 заканчиваем складывать, так как тогда сумма превысит K)
7+8=15=S2
15-10=5=R1 и 15-5=0=R2
R2<R1... то есть сортировка тут не в помощь, если я правильно понял как ты действовал

← →
default © (2003-11-13 21:54) [2]

описался
15- 15=0=R2
и дай больше инфы...максимальный размер массива, тип его элементов, возможные предположения о значении этих элементов...
(то есть, к примеру, ты знаешь, что в массиве могут быть только числа 1, 13, 56, 67, 78 или что-то подобное)

← →
Dimaxx © (2003-11-13 23:33) [3]

Выдержка из справки

Sum function

Returns the sum of the elements in an array.

Unit Math

Category

Statistical routines

function Sum(const Data: array of Double): Extended; register;

Description

Sum returns the sum of all the values in the Data array parameter.

Пардон, ошибся - SumInt!

а сколько чисел то нужно?
сначала можно найти сумму всех элементов с помощью функции, приведенной выше, и если она меньше К, то это и будет искомый набор чисел, состоящий из всех элементов массива, иначе нужно решить задачу, чем-то похожую на размен большой купюры(К в данном случае) мелкими монетами (элементами массива). Можно числа отсортировать с помощью алгоритма QuickSort для ускорения

Наиболее быстрый алгоритм получения максимальной суммы Найти похожие ветки