Czy odcinek można przedstawić jako sumę danych odcinków?

0

Mam do napisania program, który sprawdzi czy można z danych odcinków stworzyć (poprzez ich dodawanie) dany odcinek.
Specyfikacja:
Wejście:
Podane są dwie liczby n <= 10000 i k <= 10000, oznaczające kolejno n - długość odcinka który będziemy sprawdzać i k - ilość odcinków, które będziemy podawać. A następnie należy podać k długości odcinków.
Wyjście:
TAK jeżeli da się z podanych odcinków zbudować odcinek o długości n, lub NIE jeżeli nie ma takiej możliwości.

Np dla wejścia:
16 5
10
7
2
8
1

Wyjściem jest TAK, ponieważ odcinek 16 możemy utworzyć sumując odcinki o długościach 7, 8 i 1.

Głowię się z tym już 3 godziny, jakieś propozycje?

Miałem pomysł, aby sumowal kolejne kombinacje odcinkow i sprawdzal czy sa rowne odcinkowi o dlugosci n, ale nie wiem jak to skodzic.

Musze to napisac w C++.

2

dla ułożenia odcinka o długości ujemnej - nie ma sposobu: DlaDlugości(UjemnaLiczba) = false;
dla ułożenia odcinka o długości 0 - jest sposób (0 - odcinków): DlaDlugości(0) = true;
dla ułożenia odcinka o długości X - DlaDlugości(X-TablicaOdcinków[1]) or DlaDlugości(X-TablicaOdcinków[2]) or ... or DlaDlugości(X-TablicaOdcinków[k])
tablicę DlaDlugości() zaczynasz wypełniać od 1 do n

0

A nie czasami od 1 do X?

Poza tym, jeżeli n > k to co będę później wpisywać do tej tablicy? Puste elementy czy jak? Wybacz, ale nie do końca rozumiem twoje rozwiązanie.

1

16 5
10
7
2
8
1

Tb[0]=true;
Tb[1]=Tb[1-10] || Tb[1-7] || Tb[1-2] || Tb[1-8] || Tb[1-1] = true // wszystkie ujemne - false ale Tb[1-1] = Tb[0] = true
Tb[2]=Tb[2-10] || Tb[2-7] || Tb[2-2] || Tb[2-8] || Tb[2-1] = true; // bo Tb[2-2] = Tb[0] = true
Tb[3]=Tb[3-10] || Tb[3-7] || Tb[3-2] || Tb[3-8] || Tb[3-1] = true; // bo Tb[3-1] = Tb[2] = true
...

0

Teraz rozumiem i faktycznie widzę, że jest to problem plecakowy (wagi czyli ceny wynoszą po prostu 1). Na wikipedii takie czysto naukowe wyjaśnienie niewiele mi mówi, ale od czego jest internet :). Dzieki wielkie za pomoc.'

Edit:
A jednak coś mi nie działa:

Poprzednie elementy tablicy wynoszą
Tb[0] == true;
Tb[1] == true;
Tb[2] == true;
Tb[3] == true;

I dla czwórki
Tb[4]=Tb[4-10] || Tb[4-7] || Tb[4-2] || Tb[4-8] || Tb[4-1] = true; // bo Tb[4-2] = Tb[2] = true, to samo dla Tb[4-1] = Tb[3] = true;

A oczywistym jest, dla odcinków {10, 7, 2, 8, 1} nie możemy zbudować odcinka o długości 4, więc albo nie rozumiem dobrze twojego algorytmu, albo twój algorytm jest zły :), proszę mnie poprawić.

1 użytkowników online, w tym zalogowanych: 0, gości: 1