Inteligentne sumowanie liczb, aby było ich jak najmniej

Mam pewną liczbę, np. 18. Mam także kilka liczb: 3, 9, 5, 7, 3. Muszę wśród nich znaleźć jak najmniej liczb, które dadzą mi dokładanie 18 (tzn. warunek jest taki: >= 18). Nie mam jednak pomysłu, jak to rozwiązać.

Próbowałam w pętli sumować po kolei, ale to nie zawsze dobry pomysł. Dla mojego rozwiązania najmniejsza ilość liczb to 3, bo mogą być np. 3,7,9 i 9,5,7. Może ktoś podpowiedzieć?

Tu kawałek kodu w C++

#include <iostream>
using namespace std;

int main(int argc, char **argv)
{
    int liczba = 18;
    int tablica[] = {3, 9, 5, 7, 3};
    int ilosc = 5;
    int suma = 0;
    int ile = 0;
    int i = 0;

    while(suma < liczba)
    {

    }

    return 0;
}

Sortujesz nie rosnąco i dajesz sumę tylu pierwszych aby wynosiło >=18

A czy liczy się tylko najmniejsza ilość liczb czy też ma to być jak najbliżej 18?
Jeśli opcja 1 to zrób to zachłannie -> dodawaj do siebie największe liczby aż przekroczysz 18
Jeśli opcja 2 to już ciężej bo sam fakt stwierdzenia czy w danym zbiorze istnieje podzbiór sumujący się do X to jest problem NP-zupełny (subset sum)

Tzn. może być więcej niż 18, ale jak najmniej liczb. Zrobiłam to tak, dziękuję za podpowiedzi:

#include <iostream>
using namespace std;

void SortowanieBabelkowe(int *tablica, int n)
{
    int dalej=1;
	while (dalej)//sortuj az wszystko posortowane
	{
	    dalej=0;
        for (int i=0;i<n-1; i++ )
		{
            if (*(tablica+i)<*(tablica+i+1) )
			{
                int tmp;
                tmp=*(tablica+i);
                *(tablica+i)=*(tablica+i+1);
                *(tablica+i+1)=tmp;
                dalej=1;
			}
		}

	}
}

int main(int argc, char **argv)
{
    int liczba = 18;
    int tablica[] = {3, 9, 5, 7, 3};
    int ilosc = 5;
    int suma = 0;
    int ile = 0;
    int i = 0;

    SortowanieBabelkowe(tablica, ilosc);

    while(suma <= liczba)
    {
        suma += tablica[i];
        i++;
        ile++;
    }

    cout << ile << "\n";

    return 0;
}

A jednak coś jest źle. Dla liczby 6 i liczb: int tablica[] = {2, 1, 2, 1}; wylicza mi 5, a powinno być 4 ... 5-ciu liczb to ja nawet w tablicy nie mam

Czyżby wystarczyło tylko zmienić warunek w while?

while(suma < liczba)
    {
        suma += tablica[i];
        i++;
        ile++;
    }

Nie sprawdzasz nigdzie rozmiaru tablicy. Jeżeli suma wszystkich elementów w tablicy będzie mniejsza od zadanej liczby, to będziesz czytać za tablicą, czyli niewiadomoco. No i ile będzie większe niż liczba elementów

const int rozmiar = 4;

while(suma <= liczba && i < rozmiar)
{
    suma += tablica[i];
    i++;
    ile++;
}

w zasadzie to ile jest niepotrzebne bo zawsze ile = i

Ślicznie dziękuję ;)

A jeszcze takie ciekawskie pytanie. Bo sortowanie pewnie dużo czasu zajmie, jak będę miała dużo danych. Czy poza sortowaniem jest na to jakiś inny, prosty sposób?

Inny, szybszy algorytm sortowania :P. Sortowanie bąbelkowe jest najwolniejsze z możliwych i efektywne tylko dla danych prawie posortowanych.

Ok, z sortowaniem nie ma problemu, wzięłam pierwszy lepszy szczerze pisząc :P Chodzi mi o jakąś inną metodę, w ogóle BEZ SORTOWANIA. Czy nie używając sortowania można to zrobić w możliwie dobrym czasie, czy jednak zawsze, w każdym przypadku (różna ilość danych) to sortowanie zawsze będzie lepszym pomysłem? :)

@monika. wybieranie maxa ze zbioru to jest czas O(n) więc bez sortowania pesymistycznie masz O(n²) i tego nie przeskoczysz. Jeśli liczby mają określony mały zakres możesz sortować zliczając i dostaniesz wtedy O(n) dla całego algorytmu zamiast O(nlogn) w przypadku sortowania sensowną metodą (bąbelki dają O(n²)).

Ok, dziękuję panowie, już teraz rozumiem. Zostaję przy sortowaniu, napiszę sobie tylko jakieś lepsze i będzie ok;) Pozdrawiam