Сложная проблема программирования, с которой я не могу справиться

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

Let Used = list of numbers that you sum.
Let Unused = list of numbers that you DON'T sum.
Let tmpsum = 0.
Let S = desired sum you want to reach.

for ( each number x you read )
  toss a coin:
    if it's heads and tmpsum < S
      add x to Used
    else
      add x to Unused

while ( tmpsum != S )
  if tmpsum < S 
    MOVE one random number from Unused to Used
  else
    MOVE one random number from Used to Unused

print the Used list, containing the numbers you need to add to get S

Это будет намного быстрее, чем решение динамического программирования, особенно для случайных входных данных. Единственная проблема заключается в том, что вы не можете надежно определить отсутствие решения (вы можете позволить алгоритму работать несколько секунд, и если он не завершится, предположим, что решения нет) и что вы не можете быть уверены, что получите решение. с минимальным количеством выбранных элементов. Опять же, вы можете добавить некоторую логику, чтобы заставить алгоритм продолжать работать и пытаться найти решение с меньшим количеством элементов, пока не будут выполнены определенные условия остановки, но это сделает его медленнее. Однако, если вас интересует только работающее решение, и у вас МНОГО чисел, а желаемая сумма может быть ОЧЕНЬ большой, это, вероятно, лучше, чем алгоритм DP.

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

Я не знаю точно, как называется эта задача, но кажется, что это что-то вроде http://en.wikipedia.org/wiki/Knapsack_problem.

Хех, я разыграю карту «неполная спецификация» (никто не говорил, что числа не могут появляться более одного раза!) и сведу это к проблеме «внесение сдачи». Отсортируйте числа в порядке убывания, найдите первое число меньше желаемой суммы, затем вычтите его из суммы (деление и остатки могут ускорить это). Повторяйте до тех пор, пока сумма не будет равна 0 или пока не будет найдено число, меньшее суммы.

Для полноты вам нужно будет отслеживать количество слагаемых в каждой сумме и, конечно же, генерировать дополнительные последовательности, отслеживая первое используемое число, пропуская его и повторяя процесс с дополнительными числами. Это решит проблему (7 + 2 + 1) вместо (6 + 4).

Повторяя ответ других: это проблема суммы подмножества. Это может быть эффективно решено с помощью метода динамического программирования.

Еще не упомянуто следующее: проблема псевдо-P (или NP-Complete в слабом смысле).

Существование алгоритма (основанного на динамическом программировании), полиномиального по S (где S — сумма) и n (количество элементов), доказывает это утверждение.

С Уважением.

Хорошо, я написал программу на C++ для решения вышеуказанной проблемы. Алгоритм прост :-)

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

Далее я взял три стопки n, pos и sum. В первом хранится число, для которого нужно найти возможную комбинацию суммы, во втором хранится индекс массива, с которого следует начать поиск, в третьем хранятся элементы, сложение которых даст вам введенное число.

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

Позвольте мне показать пример: - найти 44 в {63,36,22,19,12,9,7,5,3,1}

первые 36 будут помещены в сумме (наибольшее число меньше 44) 44-36=8 будет помещено в n(следующее число для поиска) 7 будет помещено в сумме 8-7=1 будет помещено в n 1 будет подтолкнул в сумме

таким образом, 44=36+7+1 :-)

#include <iostream>
#include<conio.h>
using namespace std;

int found=0;
void func(int n[],int pos[],int sum[],int arr[],int &topN,int &topP,int &topS)
{
int i=pos[topP],temp;
while(i<=9)
{
    if(arr[i]<=n[topN])
    {
        pos[topP]=i;
        topS++;
        sum[topS]=arr[i];
        temp=n[topN]-arr[i];
        if(temp==0)
            {
                found=1;
                break;
        }
topN++;
        n[topN]=temp;
        temp=pos[topP]+1;
        topP++;
        pos[topP]=temp;
        break;
    }
    i++;
}
if(i==10)
{
    topP=topP-1;
    topN=topN-1;
    pos[topP]+=1;
    topS=topS-1;
    if(topP!=-1)
    func(n,pos,sum,arr,topN,topP,topS);
}
else if(found!=1)
func(n,pos,sum,arr,topN,topP,topS);
}

main()
{
int x,n[100],pos[100],sum[100],arr[10]={63,36,22,19,12,9,7,5,3,1},topN=-1,topP=-1,topS=-1;
cout<<"Enter a number: ";
cin>>x;
topN=topN+1;
n[topN]=x;
topP=topP+1;
pos[topP]=0;
func(n,pos,sum,arr,topN,topP,topS);
if(found==0)
    cout<<"Not found any combination";
else{
cout<<"\n"<<sum[0];
for(int i=1;i<=topS;i++)
    cout<<" + "<<sum[i];
}
getch();
}

Вы можете скопировать код и вставить его в свою IDE, отлично работает :-)