Zadanie Waga, podobne do problemu plecakowego

Question

Mam takie zadanie: Waga
Szukałem odpowiedzi w internecie ale znalazłem tylko "trzeba policzyć różnice między szalkami, przełożyć wszystkie wieże na jedną stronę, a następnie zastosowanie algorytmu podobnego do problemu plecakowego", nie rozumiem jak to ma działać :(

Answer 1

1* Przerzucamy wszystkie przedmioty na jedną stronę(zmieniając znak)

2* Musimy ułożyć plecak, który weźmie połowę sumy wszystkich. Jeśli mielibyśmy zwykłe przedmioty, to klasyczny plecak. Tu jest trochę ciężej, bo trzeba uniknąć powtórzeń, ale limity są takie, że przejdzie trochę siłowe podejście. Jeśli mamy wieżę z wysokością 3, to od wysokości najmniejszych(jeden, jeden+dwa, jeden+dwa+trzy) i żeby nie było powtórzeń trzeba zarymować wszystkie dp, z mniejszych wysokości. Np. jak przetwarzamy jeden+dwa+trzy, to musimy zarymować dp, z jeden, jeden+dwa. Rymowanie - poprostu trzymamy dwie tablice dp, można je na spokojnie kopiować sobie.

Takie rozwiązanie wchodzi na 100pkt.

Comments

dodam, że jest to dość popularne zadanie, jak ktoś uczy się plecaka, dlatego odpowiedziałem na tak stary post.