Buonasera a tutti, e’ da molto tempo che cerco di risolvere questo problema, ma non so come farlo.
Ho letto argomenti simili dove dicevano di utilizzare il problema dello zaino per risolvere Pranzo della nonna. Ho capito Knapsack Problem ma come lo utilizzo su questo problema?
Qualche spiegazione/aiuto?
Sì, l’idea è simile al problema dello zaino (ovvero una programmazione dinamica), ma in questo caso puoi sforare il peso massimo (a differenza dello zaino), devi però cercare di minimizzare questa sforatura. Se non ti è ancora chiaro chiedi pure.
Ciao, grazie per la risposta.
Ho alcuni dubbi da risolvere, immaginiamo di utilizzare il problema dello zaino…
Come mi devo comportare se nella mia tabella N * K genero un valore maggiore di K?
Devo memorizzarlo dentro la tabella? Se la risposta e’ no (mi pare che sia cosi’), che valore devo inserire in quella posizione?
Alla fine devo solo trovare il minimo tra tutti i valori maggiori di K generati?
Ho piu’ o meno capito teoricamente come fare, ma praticamente non so come implementarlo.
E se invece partissi proprio da K e ogni volta togliessi il nuovo peso? In questo modo non avresti problemi con la tabella, infatti il caso in cui K diventa minore o uguale a 0 è un caso base.
quindi se ho capito bene:
Basta usare il problema dello zaino partendo da K e arrivando a 0 prendendo sempre i valori piu’ piccoli, ma se trovo un valore minore di zero (significa che abbiamo trovato una delle tante somme maggiori o uguali a k) cosa bisogna fare? Non bisogna tenerlo, o sbaglio?
Se arrivi a un valore x con x < 0 allora sai che k - x può rappresentare la risposta a questo problema, in particolare tra tutti gli x che trovi sei interessato a quello che minimizza k - x
Ho provato a scrivere il codice ma non funziona, ho cercato di minimizzare la sforatura ma ci sono comunque alcune somme migliori rispetto la mia risposta, forse dovrei gestire meglio i casi in cui le somme sono negative…
Questo e’ il codice:
#include <bits/stdc++.h>
using namespace std;
int N, K;
int P[5001];
int dp[5001][5001];
int i, j;
void pv() { //print vector
for(int a = 0; a <= N; ++a) {
cout << P[a] << "\t| ";
for(int b = 0; b <= N; ++b) {
cout << dp[a][b] << ' ';
}
cout << '\n';
}
}
int main() {
ifstream cin("input.txt");
cin >> N >> K;
for(i = 1; i <= N; ++i) {
cin >> P[i];
}
for(i = 0; i <= N; ++i) dp[0][i] = K, dp[i][0] = K;
int ans = INT_MAX;
for(i = 1; i <= N; ++i) {
for(j = 1; j <= N; ++j) {
dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - 1] - P[i]);
if(dp[i][j] <= 0) {
ans = min(ans, -dp[i][j]);
}
}
}
pv();
cout << "ans : " << K + ans;
return 0;
}
Non capisco come stai affrontando il caso base: k<= 0 :
infatti nel caso in cui k sia <= 0 la risposta è 0 (infatti non devi aggiungere nient’altro).
la risposta finale sarà poi all’interno di dp agli indici della chiamata iniziale (quale potrebbe essere?)
Se provi ad utilizzare l’approccio top-down per risolvere il problema il codice risulta semplice e intuitivo perché devi solo minimizzare le chiamate tra prendere/non prendere la i-esima portata fino a soddisfare il totale minimo da prendere ma almeno K.
Successivamente puoi provare la soluzione bottom-up con lo stesso idea.
quindi basterebbe if(dp[i][j] <= 0) { dp[i][j] = 0; }, ma ancora non capisco dov’e’ la risposta…
come detto nel commento sopra se provi con un approccio top-down (ricorsivo) risulta più facile trovare la logica giusta
ho rivisto il problema e ho risolto in questo modo:
#include <bits/stdc++.h>
using namespace std;
int N, K;
bool dp[5001][10001];
int v[5001];
int main() {
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
cin >> N >> K;
int mas = INT_MAX;
for(int i = 1; i <= N; ++i) {
cin >> v[i];
if(v[i] >= K) {
mas = max(mas, v[i]);
}
}
//soluzione se c'e' un valore maggiore uguale K
if(mas != INT_MAX) {
cout << mas;
return 0;
}
sort(v, v + N);
//numero minimo di colonne
long sum = 0;
for(int i = 1; i <= N; ++i) {
if(sum >= K) break;
sum += v[i];
}
for(int i = 1; i <= N; ++i) {
for(int j = 1; j <= sum; ++j) {
if(i == 0) {
dp[i][v[i]] = 1;
break;
}
if(j == v[i]) dp[i][j] = 1;
else {
if(j < v[i]) {
dp[i][j] = dp[i - 1][j];
}
else {
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]]);
}
}
}
}
for(int i = K; i <= sum; ++i) {
if(dp[N][i]) {
cout << i;
return 0;
}
}
cout << sum;
return 0;
}
Non ho utilizzato la ricorsione, ancora faccio fatica a utilizzarla con questo problema.
Si potrebbe ottimizzare la mia soluzione?
Sì, si può ottimizzare, e la soluzione più veloce è anche la più pulita.
Possiamo notare come nel caso in cui la soluzione sia rappresentata da un unico piatto allora il suo peso deve essere maggiore o uguale a K, altrimenti (se mangio più di un piatto) la soluzione non potrà mai pesare più di 2K e nessuno dei piatti che compongono la soluzione peserà almeno K (la dimostrazione di ciò è semplice e lasciata al lettore).
Quindi posso risolvere il problema confrontando i seguenti valori (e prendendo il minimo).
- Usando il knapsack con capienza pari a 2K trovo il minimo peso maggiore di K per il quale ho una soluzione
- Il peso del piatto con peso minimo ma maggiore o uguale di K
Trovare il secondo valore che stiamo cercando è banale. Per trovare efficientemente il primo possiamo invece implementare il knapsack utilizzando i bitset. In particolare, possiamo mantenere un bitset b di dimensioni pari a 2K dove b[i]=true se esiste una combinazioni di piatti con peso pari a i. Quindi possiamo semplicemente inizializzare b come b[0] = true, b[i] = false \forall i \neq 0 e per ogni piatto x aggiornare b facendo b |= b << x. Tramite l’aritmetica dei bitset b << x corrisponde a far shiftare a sinistra di x posizioni tutti i valori del bitset, che nel nostro caso corrisponde all: “per ogni combinazione di pesi che puoi ottenere, aggiungi il peso x”. Facendo poi l’or con il vecchio valore di b otterremo in b tutte le combinazioni di pesi che possiamo comporre utilizzando i vari x processati.
Osservando attentamente l’algoritmo ci si accorge come il ragionamento che ci sta sotto è esattamente quello del knapsack, ma sostituiamo il classico loop interno con i bitset e le loro operazioni. Questo ci permette di rendere l’implementazione molto più pulita ma soprattutto di ottenere una complessità pari a O(NK/64) invece della classica O(NK).
Solitamente non apprezzo che il codice per risolvere un problema sia incollato direttamente nei thread in quanto purtroppo può risultare più distruttiva che istruttiva come cosa, ma essendo un problema classico e visto che ci sono molti thread aperti a riguardo mi permetto di caricare un esempio di soluzione, in quanto la considero molto propedeutica.
#include <bits/stdc++.h>
using namespace std;
int const MAXN = 10010; // 2 * K
bitset<MAXN> b;
int main(){
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
int N, K;
cin >> N >> K;
b[0] = true;
int ans1 = 1e9; // Piatto singolo di peso minimo che pesa almeno K
int ans2 = 1e9; // Knapsack con capienza pari a 2K
for (int i = 0; i < N; i++) {
int x;
cin >> x;
if (x >= K) {
ans1 = min(ans1, x);
} else {
b |= b << x;
}
}
for (int i = K; i < 2 * K; i++) {
if (b[i]) {
ans2 = i;
break;
}
}
cout << min(ans1, ans2) << endl;
}
1 Mi Piace
Non ci sarei mai arrivato… Bellissima soluzione!
Ma MAXN non dovrebbe essere 2K - 1?
Si è sufficiente 2K - 1, ma solitamente per evitare errori del tipo off-by-one o simili aumento sempre leggermente le varie costanti, tanto il tempo di esecuzione e la complessità rimangono sostanzialmente uguali