Ho implementato questo problema ricorsivamente utilizzando un semplice array, questo è il codice:
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#define infinito 1100000000
#define MAXN 550
using namespace std;
int N;
int vettore[MAXN];
int ricorsiva(int v[], int quanti, int minimo)
{
if(quanti == 1)
return minimo;
int localMin = infinito;
int cont = 0;
for(int i = 0; i < N; i++)
{
if(v[i] == infinito)
continue;
cont++;
if(cont == quanti)
break;
int a = v[i];
int b = infinito;
int temp = 0;
while(b == infinito)
{
temp++;
b = v[i+temp];
}
int pos_a = i, pos_b = i + temp;
int somma = a+b;
int costo = somma > 0 ? somma : -somma;
v[pos_a] = somma, v[pos_b] = infinito;
localMin = min(localMin, ricorsiva(v, quanti - 1, max(minimo, costo)));
v[pos_a] = a, v[pos_b] = b;
}
return localMin;
}
int main()
{
FILE *in, *out;
in = freopen("input.txt", "r", stdin);
out = freopen("output.txt", "w", stdout);
scanf("%d", &N);
for(int i = 0; i < N; i++)
scanf("%d", &vettore[i]);
printf("%d", ricorsiva(vettore, N, 0));
}
(Nel caso non venga formattato bene: https://pastebin.com/KF2Zjkgp)
L’unica cosa che faccio è avviare la ricorsione col vettore iniziale, poi a turno prendo due elementi di seguito (chiamiamoli A e B), al posto di A inserisco il risultato A + B, B invece viene sostituito con “infinito”, che è un modo per dire “qui non c’è assolutamente nessun numero”. (Ho provato a re-implementarlo con un vector usando .erase() per cancellare l’elemento B, ma il risultato finale è praticamente lo stesso).
Implementato così però il problema viene affrontato a forza bruta, andando fuori tempo in 95 casi su 100 ()
Qualche consiglio su come migliorare? Posso in qualche modo (che non mi viene in mente) applicare la memoizzazione o devo cambiare completamente approccio?
È giusto l’approccio ricorsivo, ma dovresti farlo in una maniera più semplice, in modo che poi ti sia più facile memorizzare (o addirittura fare una elegante bottom-up).
Ti lascio un indizio.
Alla fine hai un solo numero, che avrai ottenuto sommando due numeri A e B.
Sicuramente A l’avrai ottenuto da un certo suffisso della sequenza, B dalla parte restante.
Volevo magari sapere un indizio in più in quanto non riesco a capire come sfruttare la memoizzazione, l’unica idea che ho avuto è generare la prima combinazione e provare a generare le altre solo se hanno come picco massimo un valore più basso della prima combinazione, a quel punto sostituisco il valore massimo che una combinazione può assumere con quello appena trovato, ma mi sembra lentissima con n=500
Ti consiglio di partire da una soluzione ricorsiva al problema, magari lavorando sulle possibili sottosequenze contigue dei dati in ingresso. Fatto questo puoi aggiungere la memoizzazione, e quindi evitare di ricalcolare più volte la stessa soluzione.
L’unica soluzione ricorsiva che mi viene in mente è una semplice brute_force, ti riferisci a quella e qualcosa di più ragionato?
Ho bisogno anche di un altro consiglio: quando devo, come in una possibile brute_force , avere una struttura modificabile(che permetta anche l’eliminazione di elementi) da passare alla funzione successiva quale struttura posso usare?
Con i semplici array mi sembra molto difficile, anche perchè non posso eliminare elementi, secondo voi una deque potrebbe essere una soluzione?
L’obiettivo sarebbe un algoritmo ricorsivo in cui l’unica cosa a cambiare sono i parametri della funzione e non i dati sottostanti. In questo modo passare dalla brute force ricorsiva - esponenziale - a una dinamica con memoizzazione - polinomiale nel numero di stati possibili - diventa molto più semplice.
Ciao, io ho risolto lo stesso problema qualche mese fa e anche se la mia soluzione è lontana dall’essere ottimale è riuscita a darmi 100/100. Come hai pensato anche tu di fare, io ho eseguito una brute force applicando però la memoizzazione. Come struttura dati un array va bene per contenere l’input, mentre per la memotable personalmente ho usato una matrice.
Per quanto riguarda la funzione : non capisco quali parametri mi bastano per rappresentare una combinazione senza modificare i valori della sequenza originale.(anche un deque di indici delle coppie gia sommate credo che non mi permetta di utilizzare poi la memoizzazione)
Oltretutto non capisco nel creare una combinazione quale dato di una combinazione precedente mi può servire se non il miglior picco fino ad ora raggiunto, o sbaglio?
Chiedo venia per le mie difficoltà ma non ho troppo tempo per ragionare ai problemi in questo periodo, ma voglio comunque migliorare per il secondo round delle OIS.
Come faccio con una ricorsiva ad sapere quali valori ho già sommato e quali devo ancora sommare tra di loro senza mantenere questi dati in nessuna struttura?
Non so di preciso cosa stai provando a fare tu, ma se vuoi ti do una mano dicendoti cosa ho fatto io.
Ho creato una matrice picchi[N][N] tale che picchi[i][j] contenga il picco minimo ottenibile sommando tutti i valori dall’indice i all’indice j con i < j. Il caso base della ricorsione è quando j-i == 1 in quanto in picco è uguale a V[i]+V[j].
Non so se sono stato molto chiaro…
)
