Трудная проблема программирования, с которой у меня возникают проблемы с моей головой

Ответ 1

Вы смотрите Проблема с рюкзаком

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

Изменить: ваш специальный случай - Задача подмножества сумм

Ответ 2

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

Ответ 3

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

EDIT: нужно рассмотреть динамическое программирование.

Ответ 4

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

Ответ 5

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

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

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

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

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

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

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

Ответ 6

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

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 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 предполагает использование частичных сумм в качестве индексов массивов, а индексы могут быть естественными номера. Конечно, вы можете использовать hashtables, но это сделает решение DP еще медленнее.

Ответ 7

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

Ответ 8

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

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

Ответ 9

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

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

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

С уважением.

Ответ 10

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

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

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

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

Позвольте мне показать пример: найти 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, отлично работает: -)