sorry, ale asi jsem nepochopil, v čem je problém
jestli ty kusy navazují jako skládací metr, tak celek bude dlouhý jako nejdelší kus, ostatní kusy se složí "tam a zpět" (tedy - + - + a na jejich pořadí už nezáleží)
To jsem si myslel taky - zkuste kusy o velikosti 5, 2, 4 v tomto poradí - výsledek bude 6
No jasně, ale co ti brání to vzít v dobrém pořadí? tedy od největšího po nejmenší?
Tedy:
setřídit dřívka podle velikosti a poskládat jako skládací metr. Délka bude délka toho nejdelšího, ale "výška" metru optimální nebude.
Máte pravdu.
Jen bych doplnil, že to dobré pořadí může být například +5 -4 +2. Jako první položím ten nejdelší. A pak odečtu ten druhý nejdelší. Tím se dostanu směrem k počátku. Pokud se mohou délky opakovat, tak v nejkrajnějším případě opět do počátku. Jako další opět přičtu. Tím se opět dostanu dopředu, ale ne dále, než odkud začínal ten druhý dílek. A opět odečtu atd.
Takže algoritmus je snadný:
1. Seřadím dílky podle délky vzestupně
2. U lichých dílků dám znaménko +, u sudých znaménko -
Tím jsem získal optimální řešení, kde celková délka použitého prostoru je rovna délce nejdelšího dílku.
Použitý prostor:
X1 až Xn jsou dílky
D1 až Dn jsou jejich délky
Un je pozice, kde začíná dílek Dn, respektive končí dílek D(n-1)
1. První dílek dám plusem od nuly, U1 = 0, U2 = D1
2. Sudý dílek Xn dám mínusem od dílku X(n-1). Počátek je na Un a konec na Un-Dn
3. Lichý dílek Xn dám plusem od dílku X(n-1). Počátek je Un a konec na Un+Dn
Pro všechna n>= 2 sudá platí, že U(n-1) <= U(n+1) < Un
Pro všechna n> 2 lichá platí, že Un < U(n+1) <= U(n-1)
Z toho vyplývá, že začátek dalšího dílku (ani konec) nemůže být mimo oblast, kde byl dílek předchozí.
Jinak řečeno, když to mám seřazené, tak se žádný dílek nemůže návratem dostat jinam, než kde už byl ten předchozí.
Najde někdo nějaké zadání, pro které by to neplatilo?