Puoi leggere e provare a risolvere questo problema visitando questo indirizzo sushi
Consideriamo il problema di determinare se è possibile spendere esattamente euro ordinando al più portate di ciascun piatto: è possibile risolvere questo problema attraverso il Knapsack 0-1 in cui abbiamo copie di ciascun piatto per un totale di oggetti.
Notiamo che se possibile spendere esattamente euro con al più portate di ciascun piatto, allora è anche possibile spenderli con portate. Possiamo quindi trasformare il problema originale nel problema precedente attraverso una ricerca binaria. Il knapsack ha complessità di . Notiamo che quindi la complessità di questa soluzione è .
Lemma: dato , , tali che:
per ogni esiste tale che .
Anziché inserire volte ciascun piatto, inseriamo nel knapsack oggetti: .
Supponiamo che per spendere euro siano necessarie portate del piatto , per il lemma precedente, qualunque sia esiste un subset di oggetti con somma . In questo modo otteniamo un knapsack equivalente che tuttavia ha un numero di oggetti molto più piccolo.
La complessità del knapsack è quindi ridotta da a , quindi la complessità totale è .
Anziché eseguire una ricerca binaria sul risultato, eseguiamo una ricerca esponenziale.
Determiniamo se è possibile spendere euro con portata di ogni piatto, in caso negativo proviamo con portate, poi con , finché non troviamo un numero tale che non è possibile con ma è possibile con .
Notiamo che per il lemma precedente, ad ogni iterazione non è necessario ricostruire l'intero knapsack ma possiamo riutilizzare il risultato dell'iterazione precedente aggiungendo un oggetto di peso per ogni .
Infine dobbiamo determinare il valore di , per farlo eseguiamo una ricerca binaria tra e , come prima possiamo riutilizzare i knapsack delle iterazioni precedenti per velocizzare il calcolo.
Ad ogni iterazione eseguiamo aggiorniamo il knapsack con complessità per cui la complessità finale è .
È possibile risolvere il knapsack utilizzando i bitset, sebbene la complessità teorica rimanga uguale, in pratica è 64 volte più veloce!
#include <bits/stdc++.h>
using namespace std;
constexpr int MAXB = 100'100;
int sushi(int N, int B, vector<int> A) {
bitset<MAXB> S1, S2;
S1[0] = 1;
int R = 1;
while (true) {
S2 = S1;
for (int a : A) {
S2 |= S2 << (a * R);
}
if (S2.test(B)) break;
R *= 2;
S1 = S2;
if (R > B) return -1;
}
for (int t = R / 2; t > 0; t /= 2) {
S2 = S1;
for (int a : A) {
S2 |= S2 << (a * t);
}
if (!S2.test(B)) {
R |= t;
S1 = S2;
}
}
return R;
}