Programmazione dinamica

Buongiorno, stavo riprovando a risolvere il problema MULTICORE delle territoriali di quest’anno con la programmazione dinamica(durante la gara lo risolsi in modo greedy). Sto provando a risolverlo col problema dello zaino, ma non riesco ad allocare array grandi quanto il budget.

10^9 * 10^2 * 3 interi sono troppi da allocare in memoria, sono crica 1117GB di ram e non credo che il tuo pc ne abbia cosi tanta a disposizione :joy: Volendo allocare solo 10^9 interi sono 1GB di ram e di solito non viene mai fornita cosi tanta memoria per un problema.
Dovresti cambiare stati nella dp. Guarda bene le assunzioni e prova a pensare su cosa potresti far affidamento.
Su Wiki-olinfo puoi trovare una guida su questo problema.

2 Mi Piace

Grazie, non sapevo che avessero publicato le soluzioni.

Esistono sempre le istanze aws da 1,952 GiB. Se vuol allocare tutti i 1117 GiB sullo stack puoi utilizzare ulimit per incrementare la massima capienza altrimenti puoi allocare sull’heap.

1 Mi Piace