https://pl.spoj.pl/problems/ETI07E7/ <-- zaintrygowało mnie to zadanko. Czy istnieje jakis algorytm dynamiczny na rozwiazanie tego problemu (no albo jakis inny w miare przejrzysty)? Jesli tak, to jaki? Bo polskie google nic o tym nie wie, a angielskie to mi podaje uogolnienia na m plecakow, w dodatku jakies super wypasione algorytmy z ktorych nic nie idzie zrozumiec...
0
0
a gdyby zacząć od większego plecaka, później gdy jego wolna pojemność będzie mniejsza od mniejszego plecaka, ładować do tego drugiego i tak na zmianę?
0
Oczywiście, że się da. Zresztą algorytm uogólniony na M jest zazwyczaj dość wredny w czytaniu. Spróbuj za M podstawić 1.
Swoją drogą zadanie jest stosunkowo proste i można je rozwiązać intuicyjnie.
0
może tak
- obliczasz wagi przedmiotów (stosunek ich rozmiaru do wartości)
- sortujesz wg wagi malejąco
- sprawdzasz czy aktualny mieści się w większym - tak wkładasz go, nie - goto 5
- bierzesz następny, goto 3
- sprawdzasz czy aktualny mieści się w mniejszym - tak wkładasz go, nie -goto 6
- olewasz go i bierzesz następny, jak NIE MA to end
- goto 3
0
Misiekd, Loganek - to ma być rozwiązanie problemu, a nie algorytm jeden naiwniejszy od drugiego...
Kontrprzykład do algorutmu od Misiekd (ten Loganka jest nieoptymalny już przez oczywistość):
- plecaki: oba rozmiaru 10
- itemy: jeden (wartości 1, rozmiaru 1), dwa (wartości 9, rozmiaru 10)
Rozważałem to zadanie parę miesięcy temu, ale nie implementowałem (bo zrozumiałem, że nie jest rozwiązaniem tego zadania). Z tego, co pamiętam, algorytm wyglądał podobnie do zwykłego dynamicznego plecaka, z tym że:
- w polach tablicy trzymamy nie jedno pole (z maksymalną wartością plecaka wielkości i dla przedmiotów a_1 .. a_j), a dwa (z maksymalnymi wartościami obu plecaków
- przy kolejnych krokach nie rozważamy dwóch przypadków (przepisanie z góry lub z lewej), a trzy (przepisanie z lewej jednego, z lewej drugiego, lub obu z góry)