Dla osób które tak jak ja nie rozumieją dlaczego tam jest problem plecakowy: chcemy podzielić zbiór szczap (bez najdłuższej) na dwa podzbiory, tak, żeby minimum z ich sum było maksymalne. Oczywiście to jest wtedy gdy je podzielimy równo, więc szukamy dwóch części, które będą możliwie najbliżej siebie... no ale jedna część dopełnia drugą, więc wystarczy znaleźć jedną połowe. To jest dokładnie problem plecakowy, znajdź taki podzbiór, którego suma będzie najbliżej S/2.
Dla osób które tak jak ja nie rozumieją dlaczego tam jest problem plecakowy: chcemy podzielić zbiór szczap (bez najdłuższej) na dwa podzbiory, tak, żeby minimum z ich sum było maksymalne. Oczywiście to jest wtedy gdy je podzielimy równo, więc szukamy dwóch części, które będą możliwie najbliżej siebie... no ale jedna część dopełnia drugą, więc wystarczy znaleźć jedną połowe. To jest dokładnie problem plecakowy, znajdź taki podzbiór, którego suma będzie najbliżej S/2.
przepotężne omówienie!
Szczegóły w nowelce Nasza Szczapa
dowalone było to zadanie
Ha
porąbane
Tragiczne omówienie. Gdybym sam nie rozwiązał zadania nie miałbym pojęcia o co chodzi.
Oddajcie nam niebieskie książeczki! Albo chociaż Idziaszka.