Algoritmo da trovare O(n). HARD :(

[Giova411]

Sia $V$ un vettore di $n$ interi. Chiamiamo costo $C(i , j)$ di un sottovettore $V[i .. j]$ di $V$ la somma dei suoi elementi:

$ C(i,j) = \sum_{t=i}^j V[t] $

Una partizione k-partizione del vettore $V$ è una divisione del vettore in $k$ sottovettori
$V[1, j_1] , V[j_1 + 1 , j_2] , V[j_2 + 1 , j_3] , .. , V[j_(k-1) +1 , j_k] $ con $j_k = n $ e $j_t Chiamiamo costo della partizione il costo massimo dei suoi sottovettori. Dato un vettore V di n interi ed un intero k, con $2<= k <= n$ il problema è trovare una partizione di V di costo minimo che divide V in k sottovettori.
Ad esempio, se $ V = {2,3,7,-7,15,2}$, una 3-partizione possibile è ${2,3,7} , {-7,15} , {2} $ , che ha costo pari ha $2+3+7 = 12$. Ma la 3-partizione data da ${2,3} , {7} , {-7, 15, 2} $ ha costo pari a $-7+15+2 = 10$ e dovrebbe essere quella ottima!

1) Scrivere un algoritmo (pseudocodice) che risolve il problema nel caso $k=2$, restituendo il costo della 2-partizione ottima in $O(n)$

2) Scrivere un algoritmo (pseudocodice) che risolve il problema nel caso $k=3$, restituendo il costo della 3-partizione ottima in $O(n^2)$

3) Scrivere un algoritmo generale (pseudocodice) che risolve il problema per qualsiasi $k$, restituendo il costo della k-partizione ottima in $O(k*n^2)$

In tutti i casi discutere il costo computazionale.
---
Ovviamente i casi $k=2$ e $k=3$ possono essere risolti dall'algoritmo del punto 3 ma, per questi valori di k, si possono trovare algoritmi più efficenti e semplici. Il punto uno mi crea un po' di problemi (non che gli altri due siano semplici). Il terzo è "fattibile" con la programmazione dinamica. Nel primo punto ho pensato che se divido il vettore d'esempio (k=2) come ${2,3,7,-7} e {15,2}$ avrei il costo minimo pari a 5. Si potrebbe dividere altresì a metà ${2,3,7} e {-7, 15,2}$ ma si avrebbe costo 10.

[Giova411]

Il punti successivi pensavo di risolverli considerando l'insieme indipendente di intervalli pesati ma poi forse non mi tornano i numeri giusti.
Vabé la programmazione dinamica va vista come un "mondo a parte" quindi chiedo solo aiuto per il punto uno

[apatriarca]

La somma degli elementi di tutti i gruppi è ovviamente uguale alla somma totale degli elementi. Per cui quando passi da una combinazione ad un altra devi semplicemente sottrarre alla somma del gruppo i valori degli elementi che hai rimosso e sommare i valori degli elementi aggiunti. Nel caso \(k=2\) questo è particolarmente semplice. Puoi infatti partire calcolando la somma totale degli elementi e iniziare a considerare tutte le somme dei sottovettori ottenuti includendo nel primo sottovettore gli elementi fino all'i-esimo. L'algoritmo è lineare perché puoi aggiornare la somma dei due sottovettori semplicemente facendo una somma e una sottrazione e perché confronti tutte e \(n\) le combinazioni possibili. Il caso \(k=3\) e i successivi sono molto simili in quanto fissi il primo sottovettori e calcoli la soluzione per \(k=2\) del resto del vettore.

[Giova411]

Sì Apa come tu faccia ad arrivarci subito è incredibile.
Ho una soluzione che non mi torna proprio ma forse sono io stonato.

2partizione(integer[] V, integer n)
integer tot <-- 0
for i<--1 to n do
  tot <-- tot + V[i]
integer sofar <-- 0
integer min <-- +oo
for i<--1 to n-1 do
  sofar <-- sofar + V[i]
  min <-- min( min , max(sofar, tot - sofar) )
return min

[Giova411]

"Giova411":Nel primo punto ho pensato che se divido il vettore d'esempio (k=2) come ${2,3,7,-7} e {15,2}$ avrei il costo minimo pari a 5.

Ehm mi sa che ho scritto una cavolatina: si considera forse il massimo tra i due quindi 17.
Da qui si evince che è giusto lo pseudocodice e che sbagliavo ad interpretare il testo:
Punto 1 [Risolto]