Алгоритм для выбора значений из массива, сумма которых ближе всего к целевому значению?

Question

У меня есть массив почти отсортированных значений длиной 28 элементов. Мне нужно найти набор значений, который суммируется с целевым значением, предоставленным алгоритму (или, если точная сумма не может быть найдена, ближайшая сумма Ниже целевого значения).

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

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

Вот мой текущий алгоритм для справки. Итерация начинается с самого высокого доступного значения. Если текущее значение меньше целевой суммы, оно добавляет значение к выходным данным и вычитает его из целевой суммы. Это повторяется до тех пор, пока сумма не будет достигнута или пока не закончатся значения. Это сортирует почти восходящий отсортированный список.

//valuesOut will hold a bitmask of the values to be used (LSB representing array index 0, next bit index 1, etc)

void pickValues(long setTo, long* valuesOut)
{
    signed char i = 27;//last index in array
    long mask = 0x00000001;

    (*valuesOut) = 0x00000000;
    mask = mask<< i;//shift to ith bit
    while(i>=0 && setTo > 0)//while more values needed and available
    {
        if(VALUES_ARRAY[i] <= setTo)
        {
            (*valuesOut)|= mask;//set ith bit
            setTo = setTo - VALUES_ARRAY[i]._dword; //remove from remaining         }
        //decrement and iterate
        mask = mask >> 1;
        i--;
    }
}

Еще несколько параметров:

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

• Вполне возможно, что массив будет содержать набор значений, которые не могут создать каждую сумму в пределах своего диапазона. Если точная сумма не может быть найдена, алгоритм должен вернуть значения, которые создают следующую наименьшую сумму.

Answer 1

Эта проблема известна как проблема суммы подмножеств, которая является частным случаем задачи о ранце .Википедия - хорошая отправная точка для некоторых алгоритмов.

Answer 2

Как уже отмечали другие, это то же самое, что и оптимизационная версия задачи о подмножестве сумм, которая является NP-Complete.

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

Например, при e> 0 существует полиномиальный алгоритм времени, который использует пространство O ((n * logt) / e), (t - целевая сумма, n - размер массива), что дает вам подмножество, такое, что сумма z не менее чем в 1 / (1 + e) ​​раз оптимальна.

т.е. если наибольшая сумма подмножества была y, то алгоритм находит сумму подмножества z такую, что

z <= y <= (1+e)z

и использует пробел O ((n * logt) / e).

Такой алгоритм можно найти здесь: http://www.cs.dartmouth.edu/~ac/Teach/CS105-Winter05/Notes/nanda-scribe-3.pdf

Надеюсь, это поможет.

Answer 3

Если значения достаточно малы, это простое динамическое программирование (DP).Временная сложность будет O (n * target) и требования к памяти O (target).Если вас это устраивает, в Интернете есть множество учебных пособий по DP.Например, здесь первая обсуждаемая проблема (со счетчиками) очень похожа на вашу (за исключением того, что они позволяют использовать каждое число более одного раза):
http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=dynProg

update YepКак заметил другой человек, это простой случай проблемы с рюкзаком.