Tricky problem z programowaniem, który sprawia mi kłopot z obejrzeniem

Question

Po pierwsze, pozwól mi powiedzieć, że to nie jest praca domowa (jestem studentem A-Level, to nic nie jest tak blisko rozwiązania problemu (to jest sposób harder)), ale bardziej problem próbuję wyskoczyć, aby poprawić moją logikę programowania.

Pomyślałem o scenariuszu, w którym istnieje tablica losowych liczb całkowitych, powiedzmy na przykład 10 liczb całkowitych. Użytkownik wprowadzi numer, na który chce się liczyć, a algorytm spróbuje ustalić, jakie liczby są potrzebne do zrobienia tej sumy. Na przykład, gdybym chciał zrobić sumę 44 z tej tablicy liczb całkowitych:

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

Wyjście będzie:

36 + 3 + 5 = 44 

Albo coś w tym kierunku. Mam nadzieję, że wyrażę się jasno. Jako dodatkowy bonus chciałbym, aby algorytm wybrał jak najmniej liczb, aby uzyskać wymaganą sumę, lub podać błąd, jeśli suma nie może być wykonana z podanymi liczbami.

Pomyślałem o użyciu rekurencji i iteracji w tablicy, dodając liczby w kółko, aż suma zostanie spełniona lub minęła. Ale nie mogę zrozumieć, co zrobić, jeśli algorytm przejdzie obok sumy i musi być selektywny co do liczb do wyboru z tablicy.

Nie szukam kompletnego kodu lub kompletnego algorytmu, chcę tylko, abyś miał opinię na temat tego, jak powinienem to zrobić i być może podzielę się kilkoma wskazówkami lub czymś. Prawdopodobnie rozpocznę pracę nad dzisiejszym wieczorem. : P

Jak powiedziałem, nie zadanie domowe. Tylko ja chcę zrobić coś bardziej zaawansowanego.

Dziękujemy za pomoc, którą możesz zaoferować. :)

Answer 1

Szukasz w Knapsack Problem

Problem plecakowy problem lub plecak jest to problem występujący w optymalizacji kombinatorycznej: Biorąc pod uwagę to zestaw elementów, każdy o wadze i wartości, określić liczbę każdego element, który ma zostać uwzględniony w zbiorze, aby całkowita waga była mniejsza od podanego limitu, a całkowita wartość jest tak duża, jak to możliwe. Nazwa pochodzi od problemu, z którym boryka się ktoś, kto jest ograniczony przez plecak o stałym rozmiarze i musi go wypełnić najbardziej przydatnymi przedmiotami.

---

Edit: Twój szczególny przypadek jest Subset Sum Problem

Answer 2

Czy subset sum zrobi? ;]

Answer 3

Nie wiem dokładnie co to zadanie nazywa, ale wydaje się, że jest to rodzaj http://en.wikipedia.org/wiki/Knapsack_problem.

Answer 4

Jest to klasyczny problem, który można znaleźć na kursie na poziomie uczelni (lub przynajmniej wtedy go widziałem). Najlepiej popracować nad tym na papierze, a rozwiązanie w kodzie powinno być stosunkowo łatwe do opracowania.

EDYCJA: Jedna rzecz do rozważenia jest dynamic programming.

Answer 5

Twój problem jest związany z subset sum problem. Musisz wypróbować wszystkie możliwe kombinacje w najgorszym przypadku.

Answer 6

Brak skrótów tutaj obawiam się. Oprócz tego, co inni powiedzieli, o jakim konkretnym problemie to jest itp., Oto kilka praktycznych porad, które oferują ci punkt wyjścia:

Chciałbym posortować tablicę i podać sumę wejściową m, znajdę pierwszy numer w tablicy mniejszej niż m, zadzwoń pod numer n (jest to twoja pierwsza możliwa liczba dla sumy) i zacznij od najwyższego możliwego dopełnienia (m-n), idąc w dół.

Jeśli nie znaleźć precyzyjne dopasowanie, wybierz najwyższy dostępny, nazwać o, (który teraz jest 2-ty numer) i poszukaj 3rd jednego począwszy od ( m-n-o) i znowu w dół swój sposób pracy.

Jeśli nie znajdziesz dokładnego dopasowania, zacznij od następnej liczby n (indeksu oryginału n w indeksie 1) i zrób to samo. Możesz to robić, dopóki nie znajdziesz dokładnego dopasowania dla dwóch liczb. Jeśli nie znaleziono dopasowania dla sumy dla dwóch liczb, rozpocznij proces ponownie, ale rozwiń go, aby dołączyć trzeci numer. I tak dalej.

Można to zrobić rekurencyjnie. Przynajmniej takie podejście zapewnia, że ​​po znalezieniu dopasowania będzie to ta z najmniejszymi możliwymi liczbami w zbiorze, która będzie stanowić sumę sumy wejściowej.

Potencjalnie, najgorszy przypadek, w końcu przejdziecie przez cały los.

Edytuj: Jak Venr poprawnie wskazuje, moje pierwsze podejście było nieprawidłowe. Zmieniono podejście, aby to odzwierciedlić.

Answer 7

Heh, będę grać „niekompletny specyfikacji” karty (nikt nie powiedział, że numery nie może pojawić się więcej niż jeden raz!) I zredukować do „dokonywania zmian” problemu. Posortuj liczby w porządku malejącym, znajdź pierwsze mniej niż żądana suma, a następnie odejmij od swojej sumy (podział i resztki mogą przyspieszyć). Powtarzaj aż do sumy = 0 lub bez liczby mniejszej niż suma zostanie znaleziona.

Aby uzyskać kompletność, należy śledzić liczbę dodatków w każdej sumie i oczywiście generować dodatkowe sekwencje, śledząc pierwszy numer, którego używasz, pomijając to i powtarzając proces z dodatkowymi numerami . Rozwiązałoby to problem (7 + 2 + 1) nad (6 + 4).

Answer 8

Istnieje bardzo skuteczny randomizowany algorytm dla tego problemu. Wiem, że już zaakceptowałeś odpowiedź, ale cieszę się, że mogę się nią podzielić, mam tylko nadzieję, że ludzie nadal będą sprawdzać to pytanie :).

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 

To będzie dużo szybsze niż rozwiązanie do programowania dynamicznego, szczególnie w przypadku losowych danych wejściowych. Jedyne problemy to, że nie można wiarygodnie wykryć, kiedy nie ma rozwiązania (można pozwolić uruchomić algorytm na kilka sekund, a jeśli to nie zakończy, zakładamy, że nie ma rozwiązania) oraz, że nie możesz być pewien, że masz rozwiązanie z minimalną liczbą wybranych elementów. Ponownie, można dodać trochę logiki, aby algorytm nie poddawać się i próbuje znaleźć rozwiązanie z mniejszą ilością elementów, dopóki nie zostaną spełnione pewne warunki zatrzymania, ale uczyni to wolniej. Jednakże, jeśli jesteś zainteresowany tylko w roztworze, który działa i masz dużo liczb i pożądany suma może być bardzo duża, to chyba lepiej niż algorytmu DP.

Kolejną zaletą tego podejścia jest to, że będzie działać także dla liczb ujemnych i wymiernych bez żadnych modyfikacji, co nie jest prawdą dla rozwiązania DP, ponieważ rozwiązanie DP wymaga użycia sum częściowych jako wskaźników tablicy, a indeksy mogą być tylko liczby naturalne.Możesz oczywiście używać hokerów, ale to spowoduje, że rozwiązanie DP będzie wolniejsze.

Answer 9

Powtarzanie odpowiedzi innych: jest to problem z sumą podzbiorów. Można to skutecznie rozwiązać za pomocą techniki programowania dynamicznego.

Nie wymieniono jeszcze następujących: problemem jest Pseudo-P (lub NP-Complete w słabym tego słowa znaczeniu).

Istnienie algorytmu (opartego na programowaniu dynamicznym) wielomianu w S (gdzie S jest sumą) i n (liczba elementów) potwierdza to twierdzenie.

Pozdrawiam.

Answer 10

Ok, napisałem program w C++, aby rozwiązać powyższy problem. Algorytm jest prosty :-)

Przede wszystkim ułóż dowolną tablicę w porządku malejącym (mam zakodowaną tablicę w malejącej formie, ale możesz zastosować dowolny z algorytmów sortowania).

Następnie wziąłem trzy stosy n, pos i sumę. Pierwszy zapisuje numer, dla którego można znaleźć możliwą kombinację sum, drugi zawiera indeks tablicy gdzie można rozpocząć wyszukiwanie, trzeci przechowuje elementy, których dodanie da ci wpisany numer.

Funkcja szuka największej liczby w tablicy, która jest mniejsza lub równa wprowadzonej liczbie. Jeśli jest równy, po prostu przesuwa liczbę na stos sum. Jeśli nie, to wypycha napotkany element tablicy do stosu sum (tymczasowo) i znajduje różnicę między liczbą do wyszukania i liczbą napotkanych, a następnie wykonuje rekursję.

Pokażę przykład: - aby znaleźć w {44} 63,36,22,19,12,9,7,5,3,1

pierwszy 36 zostanie wciśnięty w sumie (największy liczba jest mniejsza niż 44) 44-36 = 8 zostanie wsunięty n (numer kolejnego szukać) 7 zostanie wciśnięty w sumie 8-7 = 1 zostanie wsunięty n 1 zostanie wsunięty sumy

zatem 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(); 
} 

Możesz skopiować kod i wkleić go do swojego IDE, działa dobrze :-)