Ti do qualche consiglio su come approcciare il problema per ottenere una soluzione più veloce. La prima osservazione è che k \leq 5000 ma p_i \leq 1000000 quindi potrebbe accadere che molti dei cibi proposti risultino poco utili in quanto pesano troppo. Allora possiamo iniziare ordinare i cibi per il loro peso e possiamo notare che:
Se il cibo di peso minore ha un peso maggiore o uguale a k allora il suo peso rappresenta la risposta al problema.
Se la condizione 1 non è vera significa che almeno una portata ha peso minore di k e quindi la soluzione che stiamo cercando potrebbe essere composta dalla composizione di più di una portata, anche in questo caso abbiamo due casi:
2.1 Ho un’unica portata che pesa meno di k, allora in questo caso la soluzione migliore consiste nel prendere la seconda portata di peso minimo perché effettivamente della portata che pesa di k non me ne posso fare nulla di utile.
2.2 Se ho almeno due portate che pesano meno di k allora potrebbe essere che la soluzione finale consista sempre nel prendere un’unica portata (che sarà sempre la portata di peso minore tra quelle con peso maggiore o uguale a k), oppure mi conviene prendere un insieme S di m portate con pesi s_1, s_2, \dots, s_m e m \geq 2. L’osservazione fondamentale è che, se S è la soluzione ottimale allora nessuna di queste portate potrà pesare almeno k, infatti se fosse così potremmo rimuovere tutte le altre portate dall’insieme ottenendo una soluzione migliore che risulta comunque valida. Ora che sappiamo che s_i \leq k\forall i = 1 \dots m possiamo anche notare che la somma dei pesi delle portate T = \Sigma_{i = 1}^{m}s_i non può superare 2k - 1, infatti se fosse così potrei togliere uno dei qualsiasi elementi di S (che ricordo essere minori di k) ottenendo una soluzione valida migliore.
Riassumendo i punti precedenti possiamo dire che l’insieme delle portate della soluzione è formato da una sola portata oppure tutte le portate che lo compongono hanno un peso minore di k e la loro somma sarà minore di 2k. Quindi quando effettui il knapsack puoi tenere conto di tali osservazioni per ridurre il numero di elementi da processare. Inoltre io ti consiglio di scrivere una soluzione iterativa che risulta più veloce, so che inizialmente potrebbe essere meno intuitiva ma è comunque semplice. Vedi cosa riesci a fare al più poi ti faccio vedere come implementarla.
Inoltre, ma questo topic lo riprenderei una volta che riesci a fare 100 utilizzando le dritte che ti ho dato prima, esiste un altro modo che utilizza una struttura dati particolare per risolvere il problema in maniera molto veloce e con un codice schifosamente corto e semplice.
Ciao, grazie per aver risposto.
Ho gia’ risolto il problema utilizzando una soluzione iterativa e riesco a passare tutti i test case solo che voglio provare anche a risolverlo in modo ricorsivo. Ora cerco di ottimizzare l’algoritmo usando i consigli che mi hai dato, ti faro’ sapere se riusciro’ ad ottimizzarlo.
int mangia(int N, int K, int P[]) {
int min=P[0];
for (int i=0; i<N; i++) {
if (P[i] < min)
min = P[i];
if (P[i] < K)
return knapsack(N, 0, K, P);
}
return min;
}
Aggiungendo questa cosa, la quantità di timeout rimane esattamente la stessa per me (60/100), quindi ne deduco che il primo accorgimento non sia effettivamente utile, purtroppo.
Proverò ad aggiungere gli altri per vedere se funzionano.
Diciamo che il primo accorgimento serve per fare in modo che, utilizzando anche il secondo accorgimento, si coprano tutti i possibili casi. Quindi ti servono entrambi gli accorgimenti. Anche perché se fosse stato sufficiente il primo accorgimento allora avrei presentato solamente quello.
#include <cassert>
#include <fstream>
#include <vector>
#include <unordered_map>
#include <algorithm>
#include <iostream>
using namespace std;
int nonAbbastanza = 1000000000;
int mangia(short N, short K, vector <int> P, short index, unordered_map <short, int> memo) {
if (K <= 0)
return 0;
if (N == index)
return nonAbbastanza;
if (memo.find(index) != memo.end())
return memo[index];
int minimo = min(mangia(N, K, P, index + 1, memo), mangia(N, K - P[index], P, index + 1, memo) + P[index]);
memo[index] = minimo;
return minimo;
}
int main() {
FILE* fr, * fw;
short N, K;
fr = fopen("input.txt", "r");
fw = fopen("output.txt", "w");
assert(2 == fscanf(fr, "%hu %hu", &N, &K));
vector <int> P(N);
for (int i = 0; i < N; i++)
assert(1 == fscanf(fr, "%d", &P[i]));
sort(P.begin(), P.end());
if (P[0] >= K)
fprintf(fw, "%d\n", P[0]);
else if (P[1] >= K)
fprintf(fw, "%d\n", P[1]);
else {
int somma = 0;
short j;
for (j = 0; j < N && somma < 2*K; j++){
somma += P[j];
}
fprintf(fw, "%d\n", mangia(j, K, P, 0, {}));
}
fclose(fr);
fclose(fw);
return 0;
}
Ho cercato di implementare i consigli prima citati (spero correttamente) ma continuo ad andare in Time Out in 8 casi. Ho sbagliato qualcosa? Ci sono altre condizioni da poter implementare?
Ciao, il tuo algoritmo funziona correttamente, ma è la tua tabella degli stati memo richiamata ad agni ricorsione che porta il programma in TLE.
Anche utilizzando un’altra struttura dati al posto di unordered_map non risolvi il problema di TLE.
Una soluzione, con i constraints del task, è quella di usare una tabella globale a doppia entrata in cui memorizzare gli stati memo[K][index].