Zadanie Kolekcjoner Monet, programowanie dynamiczne

pytanie zadane 10 czerwca 2023 w Algorytmy przez pasjonat_algorytmiki Pasjonat (19,560 p.)

Mam problem z takim zdaniem:

Pewnie wejdzie tu jakieś dp, a dokładniej plecak. Napisałem kod w O(N^2 * K), zakładając, że nie używam danego przedmiotu i robię prosty plecak z pozostałymi w celu sprawdzenia, czy mogę ułożyć K pozostałymi. Dostaję 50pkt. Bardzo prosiłbym o hinta jak to przyśpieszyć.

Kod:

#include <iostream>
#include <vector>

using namespace std;

int n = 0, k = 0, wczytana_liczba = 0, cnt = 0;
vector<bool> visited;
vector<bool> dp;
vector<int> A;
vector<int> sprawdzane;
vector<int> do_dodania;

inline bool czy_pasuje(int x)
{
    dp.assign(k+1,false);
    dp[0] = true;
    sprawdzane = vector<int>();
    sprawdzane.push_back(0);
    for (int i = 0; i < n; ++i)
    {
        if (i == x)
            continue;
        do_dodania = vector<int>();
        for (int j = sprawdzane.size()-1; j >= 0; --j)
        {
            int val = sprawdzane[j];
            if (val + A[i] <= k and dp[val] == true and dp[val+A[i]] == false)
            {
                do_dodania.push_back(val+A[i]);
                dp[val+A[i]] = true;
            }
            if (dp[k] == true)
                return true;
        }
        for (int j = do_dodania.size()-1; j >= 0; --j)
            sprawdzane.push_back(do_dodania[j]);
    }
    return false;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> k;

    visited.assign(k+1,false);
    for (int i = 0; i < n; ++i)
    {
        cin >> wczytana_liczba;
        visited[wczytana_liczba] = true;
    }

    for (int i = 1; i <= k; ++i)
        if (visited[i] == true)
            A.push_back(i);

    for (int i = 0; i < n; ++i)
    {
        if (czy_pasuje(i) == false)
        {
            cout << A[i] << ' ';
            ++cnt;
        }
    }

    if (cnt == 0)
        cout << "OK";
    cout << '\n';

    return 0;
}

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

komentarz 10 czerwca 2023 przez pasjonat_algorytmiki Pasjonat (19,560 p.)

Jedyne spostrzerzenie jakie poczyniłem w kierunku czegoś szybszego to to, że jak chcemy ułożyć sumę K, to użyjemy co najwyżej sqrt(K) przedmiotów.

komentarz 11 czerwca 2023 przez pasjonat_algorytmiki Pasjonat (19,560 p.)

Mam kod na 96pkt, to samo tylko, że na bitsecie robię, i mam O(N^2 * K / 32), nie wiem jak to przyśpieszyć. Kod:

#include <iostream>
#include <vector>
#include <bitset>
#include <algorithm>

using namespace std;

int n = 0, k = 0, wczytana_liczba = 0, cnt = 0;
vector<int> A;
vector<int> ile;

const int SIZE = 10'000;
bitset<SIZE+5> B;

inline bool czy_pasuje(int x)
{
    B = bitset<SIZE+5>();
    B.set(0);
    for (int i = 0; i < n; ++i)
    {
        if (i == x)
            continue;
        B = (B | (B << A[i]));
        if (B[k] == 1)
            return true;
    }
    return false;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> k;

    ile.assign(k+1,0);
    for (int i = 0; i < n; ++i)
    {
        cin >> wczytana_liczba;
        ++ile[wczytana_liczba];
    }

    for (int i = 1; i <= k; ++i)
        for (int j = 0; j < ile[i]; ++j)
            A.push_back(i);

    for (int i = 0; i < n; ++i)
    {
        if (czy_pasuje(i) == false)
        {
            printf("%d ",A[i]);
            ++cnt;
        }
    }

    if (cnt == 0)
        printf("OK\n");

    return 0;
}

1 odpowiedź

odpowiedź 12 czerwca 2023 przez Whistleroosh Maniak (57,400 p.)
wybrane 14 czerwca 2023 przez pasjonat_algorytmiki

Najlepsza

Jest pewien trick, który pozwala liczyć szybko dp pomijając jeden element. Korzysta z dziel i zwyciężaj. Działa mniej więcej tak:

Bierzesz wszystkie monety, dzielisz je na pół. Na jednej połowie liczysz dp (czyli to co robisz tutaj B = (B | (B << A[i]))) a drugą znowu dzielisz na pół i powtarzasz rekurencyjnie. W końcu nie będzie można dzielić na pół bo zostanie tylko jeden element. Czyli dostaniesz dp pomijające ten jeden element.

Jeśli dobrze licze to będzie działać O(nlogn*k)