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!