• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Zadanie Waga, podobne do problemu plecakowego

VPS Starter Arubacloud
0 głosów
151 wizyt
pytanie zadane 28 listopada 2020 w Algorytmy przez wojtek_suchy Mądrala (6,880 p.)

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ć :(

1 odpowiedź

+1 głos
odpowiedź 30 marca 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
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.
komentarz 30 marca 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
dodam, że jest to dość popularne zadanie, jak ktoś uczy się plecaka, dlatego odpowiedziałem na tak stary post.

Podobne pytania

0 głosów
4 odpowiedzi 471 wizyt
pytanie zadane 23 stycznia 2020 w Offtop przez Ehlert Ekspert (212,630 p.)
0 głosów
2 odpowiedzi 396 wizyt
pytanie zadane 1 września 2018 w Offtop przez MarcinGuziorHombre Początkujący (320 p.)

92,455 zapytań

141,263 odpowiedzi

319,099 komentarzy

61,854 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Akademia Sekuraka 2024 zapewnia dostęp do minimum 15 szkoleń online z bezpieczeństwa IT oraz dostęp także do materiałów z edycji Sekurak Academy z roku 2023!

Przy zakupie możecie skorzystać z kodu: pasja-akademia - użyjcie go w koszyku, a uzyskacie rabat -30% na bilety w wersji "Standard"! Więcej informacji na temat akademii 2024 znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...