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

Zadanie waga z finału IX OI, przyśpieszenie dp, problem plecakowy, dynamik

VPS Starter Arubacloud
0 głosów
386 wizyt
pytanie zadane 24 lutego 2023 w Algorytmy przez pasjonat_algorytmiki Pasjonat (19,540 p.)

Mam problem z takim zadaniem: https://szkopul.edu.pl/problemset/problem/rM5z02XMy26GufAAAC03fjcB/site/?key=statement

Niewątpliwie narzuca się, że trzeba użyć problemu plecakowego. Napisałem kod na 18pkt, w O(N * K^2), gdzie K, to suma wszystkich przedmiotów. Na początku naliczam plecak, jakie sumy mogę osiągnąć, w O(N * K), potem idę po wszystkich sumach od góry, to jeśli mogę ją osiągnąć, to wywalam te przedmioty, którymi ją osiągnąłem, i odpalam drugi plecak, już bez tych przedmiotów. O(N * K^2), bo K razy odpalę plecak w O(N * K).

Nie wiem jak to przyśpieszyć, ale mam pewien pomysł, nie wiem czy dobry, i też nie pełny, ale myślałem, żeby zamiast czy da się dojść, to naliczać dp - na ile sposobów moge osiągnąć daną sumę, i potem jak idę od góry po wszystkch k, to żeby nie puszczać od nowa plecaka, tylko wziać te n elementów, którymi robiłem tą sumę, i kulturalnie odjąć do dp z nich. Tylko sa 2 problemy:

1 - Nie wiem, czy to działa, bo wygląda to podejrzanie

2 - Wartości dp mogą być zbyt duże (wydaje mi się, ze nawet 2^N), więc mogą przekroczyć zasięg unsigned long long.

Jak ma ktoś pomysł, czy mogę to tak zrobić, a jak nie to jakiś inny pomysł, to z góry dziekuję za pomoc!

Kod w O(N * K^2), dający 18pkt:

#include <iostream>
#include <vector>

using namespace std;

int n = 0, wczytana_liczba = 0;
int MAX_DP_SIZE = 0;
vector<int> liczby;
vector<int> wyn1;
vector<int> wyn2;

int main()
{
    // O(N * K * K)
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    for (int i = 0; i < n; ++i)
    {
        cin >> wczytana_liczba;
        liczby.push_back(wczytana_liczba);
        MAX_DP_SIZE += wczytana_liczba;
    }

    MAX_DP_SIZE++;
    bool dp1[MAX_DP_SIZE] = {false};
    int idx_poprzedniego[MAX_DP_SIZE] = {-1};

    dp1[0] = true;

    for (int i = 0; i < n; ++i)
    {
         for (int j = MAX_DP_SIZE; j >= 0; --j)
         {
             if (j + liczby[i] <= MAX_DP_SIZE)
             {
                  if (dp1[j] == true && dp1[j+liczby[i]] == false)
                  {
                      dp1[j+liczby[i]] = true;
                      idx_poprzedniego[j+liczby[i]] = j;
                  }
             }
         }
    }

    for (int i = MAX_DP_SIZE / 2; i >= 1; --i)
    {
        if (dp1[i] == true)
        {
            wyn1.clear();
            wyn2.clear();
            int wsk = i;
            while(true)
            {
                if (idx_poprzedniego[wsk] == -1)
                    break;
                wyn1.push_back(wsk - idx_poprzedniego[wsk]);
                wsk = idx_poprzedniego[wsk];
            }

            bool dp2[MAX_DP_SIZE] = {false};
            int idx_poprzedniego2[MAX_DP_SIZE] = {-1};
            dp2[0] = true;

            int wystapienia[MAX_DP_SIZE] = {0};
            for (int j = 0; j < wyn1.size(); ++j)
                wystapienia[wyn1[j]]++;

            for (int j = 0; j < n; ++j)
            {
                if (wystapienia[liczby[j]] > 0)
                    wystapienia[liczby[j]]--;
                else
                {
                    for (int k = MAX_DP_SIZE; k >= 0; --k)
                    {
                        if (k + liczby[j] <= MAX_DP_SIZE)
                        {
                            if (dp2[k] == true && dp2[k+liczby[j]] == false)
                            {
                                dp2[k+liczby[j]] = true;
                                idx_poprzedniego2[k+liczby[j]] = k;
                            }
                        }
                    }
                }
            }

            if (dp2[i] == true)
            {
                int wsk = i;
                while(true)
                {
                    if (idx_poprzedniego2[wsk] == -1)
                        break;
                    wyn2.push_back(wsk - idx_poprzedniego2[wsk]);
                    wsk = idx_poprzedniego2[wsk];
                }
                cout << wyn1.size() << " " << wyn2.size() << '\n';
                for (int j = 0; j < wyn1.size(); ++j)
                    cout << wyn1[j] << " ";
                cout << endl;
                for (int j = 0; j < wyn2.size(); ++j)
                    cout << wyn2[j] << " ";
                return 0;
            }
        }
    }

    cout << "0" << '\n';

    return 0;
}

Z góry dziękuję za pomoc i poświęcony czas!

komentarz 24 lutego 2023 przez Whistleroosh Maniak (56,980 p.)

i kulturalnie odjąć do dp z nich

możesz wyjaśnić o co dokładnie chodzi w tym kroku?

komentarz 24 lutego 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
edycja 24 lutego 2023 przez pasjonat_algorytmiki

Jak wcześniej szedłem po wszystkich dp w sensie:

int ile_dodalem[n][MAX_size] = wszedzie 0.

for (int j = MAX_size; j >= 0; --j)
{
    dp[j + liczby[i]] += dp[j]
    ile_dodalem[i][j + liczby[i]] = dp[j]
}

to teraz przy odjęciu:

for (int j = MAX_size; j >= 0; --j)
{
    dp[j + liczby[i]] -= ile_dodalem[i][j+liczby[i]]
}

Tylko nwm czy tak moge, bo to jest baaaardzo podejrzane.

komentarz 24 lutego 2023 przez Whistleroosh Maniak (56,980 p.)
Raczej nie będzie działać. Możliwe chyba że za dużo coś odejmiesz i wyjdzie nawet ujemnie
komentarz 24 lutego 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
no to moje pomysły się skończyły.

1 odpowiedź

0 głosów
odpowiedź 24 lutego 2023 przez Whistleroosh Maniak (56,980 p.)
Rozwiązanie jest całkiem proste (przynajmniej do zaimplementowania) i korzysta z 2 obserwacji. To zadanie najlepiej rozwiąząć w 2 fazach.

1) Spróbuj znaleźć rozwiązanie działające w O(NK). To wciaż będzie za wolne, ale w 2. fazie przyspieszymy to. Kluczowe jest zaobserwowanie co się dokładnie dzieje, gdy podczas pierwszego liczenia dp zamiast dp1[j+liczby[i]] == false byłoby dp1[j+liczby[i]] == true. Aktualnie nic z tym nie robisz, a można z tego już wyciągnąć podział na 2 zbiory.

2) Trzeba uporać się z duplikatami. Zobacz, że gdyby wszystkie odważniki miały inną wagę to mielibyśmy ich maksymalnie ok. sqrt(K) (dlaczego?). Zastanów się w jakiej sytuacji na obu szalkach może znajdować się odważnik o tej samej wadze. Ta sytuacja będzie specyficzna i jesteśmy w stanie szybko obliczyć dla niej wynik. Teraz spróbujmy policzyć dp tak samo jak poprzednio ale jeśli jest kilka odważników o tej samej wadze to będziemy aktualizowali dp nimi wszytkimi na raz. Trzeba tylko wymyślić jak. Ostatecznie dostaniemy rozwiązanie O(min(sqrt(K), N)*K)
komentarz 25 lutego 2023 przez Whistleroosh Maniak (56,980 p.)
edycja 25 lutego 2023 przez Whistleroosh
Pytanie co gdy ciężarek który usuwamy jest najcięższym w obu zbiorach. Ale wtedy wystarczy zauważyć, że możemy wziąć ten najcieższy ciężarek i jego duplikat i tylko z nich zrobić te 2 zbiory. I to jest rozwiązanie w O(NK)
komentarz 25 czerwca 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)

@Whistleroosh, 

Już rozumiem chyba wszystko. Zastanawia mnie tylko, czy jak robie tą sztuczkę z sqrt, to jak A[i] >= sqrt to wiadomo zachłan, i jak mam te <= sqrt no to robić to normalnie plecak z kolejką monotonniczną jak banknoty z OI, czy da się jakoś prościej niż ten plecak z kolejką monotonniczną?

1
komentarz 25 czerwca 2023 przez Whistleroosh Maniak (56,980 p.)
Spojrzę na to za tydzień jak mi się sesja skończy.
komentarz 27 czerwca 2023 przez Whistleroosh Maniak (56,980 p.)
Nie pamiętam jak się robi banknoty, ale tu nie trzeba rozpatrywać przypadków <= lub >= sqrt. Po prostu grupujesz wszystkie przedmioty o tej samej masie i tylko raz przechodzisz przez tablice dp dla danej masy.
komentarz 27 czerwca 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
aha no wsumie racja

Podobne pytania

0 głosów
1 odpowiedź 163 wizyt
pytanie zadane 28 listopada 2020 w Algorytmy przez wojtek_suchy Mądrala (6,880 p.)
0 głosów
1 odpowiedź 138 wizyt
0 głosów
1 odpowiedź 706 wizyt
pytanie zadane 1 maja 2023 w Algorytmy przez pasjonat_algorytmiki Pasjonat (19,540 p.)

92,845 zapytań

141,787 odpowiedzi

320,861 komentarzy

62,178 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.

Wprowadzenie do ITsec, tom 2

Można już zamawiać tom 2 książki "Wprowadzenie do bezpieczeństwa IT" - będzie to około 650 stron wiedzy o ITsec (17 rozdziałów, 14 autorów, kolorowy druk).

Planowana premiera: 30.09.2024, zaś planowana wysyłka nastąpi w drugim tygodniu października 2024.

Warto preorderować, tym bardziej, iż mamy dla Was kod: pasja (użyjcie go w koszyku), dzięki któremu uzyskamy dodatkowe 15% zniżki! Dziękujemy zaprzyjaźnionej ekipie Sekuraka za kod dla naszej Społeczności!

...