Сложная проблема программирования, из-за которой у меня возникают проблемы

Question

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

Я подумал о сценарии, в котором есть массив случайных целых чисел, например, скажем, 10 целых. Пользователь введет число, на которое он хочет сосчитать, и алгоритм попытается определить, какие числа необходимы для получения этой суммы. Например, если я хочу сделать сумму 44 из этого массива целых чисел:

myIntegers = array(1, 5, 9, 3, 7, 12, 36, 22, 19, 63);

Вывод будет:

36 + 3 + 5 = 44

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

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

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

Как я уже сказал, не домашняя работа. Просто я хочу сделать что-то более продвинутое.

Спасибо за любую помощь, которую вы можете предложить. :)

Answer 1

Вы смотрите на проблему Рюкзак

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

---

Редактировать: Ваш особый случай - * Сумма подмножества

Answer 2

Будет ли подмножество делать? ;]

Answer 3

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

РЕДАКТИРОВАТЬ: Одна вещь, чтобы рассмотреть это динамическое программирование .

Answer 4

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

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 еще медленнее.

Answer 5

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

Я бы отсортировал массив и получил бы входную сумму m, нашел бы первое число в массиве меньше m, назвал бы его n (это ваше первое возможное число для суммы) и запустил бы из максимально возможного дополнения (m-n), двигаясь вниз.

Если вы не нашли точного совпадения, выберите самое высокое из доступных, назовите его o (теперь это ваш второй номер) и найдите третий, начиная с (m-n-o), и работайте Ваш путь снова вниз.

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

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

Потенциально, в худшем случае, вам придется пройти через весь лот.

Редактировать : Как правильно заметил Венр, мой первый подход был неверным. Отредактированный подход, чтобы отразить это.

Answer 6

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

Answer 7

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

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

Наличие алгоритма (основанного на динамическом программировании) полинома от S (где S - сумма) и n (количество элементов) подтверждает это утверждение.

Привет.

Answer 8

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

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

Answer 9

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

Answer 10

Хорошо, я написал программу на 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 будет толкаться в п 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, отлично работает: -)