Tavola rotonda - Algoritmo costo minimo

Non capisco l'uso di c e f nel tuo codice. Sarebbe bello se potessi spiegarti un po 'su questo. Inoltre non ho trovato la necessità di iterare i-2 e i-1 per ogni i. (Non sono ancora in grado di commentare i post) Ora ti darò il mio algoritmo per risolvere questo problema in modo simile al tuo approccio.

Mantenere un dp [n] [2]. dp [i] [0] è per i casi che iniziano da 0 e dp [i] [1] per quelli a partire da 1. Ora per ogni i, potresti semplicemente ottenere l'elemento dp [i] [0] th come dp [ i-2] [0] + k [i] e dp [i] [1] come dp [i-2] [1] + k [i]. Il trucco è di farlo solo quando appropriato. Qui per i casi in cui i% 2 è uguale a 0, puoi supporre che quelli sono quelli che saranno coperti quando iniziamo da 0 e il resto degli elementi vale per l'altro caso. Caso d'angolo sarà quello di evitare l'ultimo elemento per il caso di partire da 0 come il tavolo è circolare.

Ecco il mio codice di lavoro. Funziona per il caso che hai appena menzionato. Non sono un membro del sito, quindi non sono in grado di provare altri casi.

#include<vector>
#include<iostream>
#include<cmath>
using namespace std;

int main() {
int n, i, j, temp;
vector<int> k;
cin>>n;
for(i=0;i<n;i++) {
cin>>temp;
k.push_back(temp);
}
int dp[n][2];
/* 0 will contain the case of starting from 0
* 1 will contain the case of starting from 1 */
dp[0][0] = k[0];
dp[0][1] = 0;
dp[1][0] = k[0]; // assign the previous value itself 
dp[1][1] = k[1];

for(i=2;i<n;i++) {      
    if(i%2 == 0) {
        // case of strting from 0 . 


        dp[i][0] = dp[i-2][0] + k[i];
        dp[i][1] = dp[i-1][1];              
    }
    else{ // case of starting from 1
        dp[i][0] = dp[i-1][0];
        dp[i][1] = dp[i-2][1] + k[i];           
    }       
}
cout<<min(dp[n-1][0], dp[n-1][1]);
 }

Quindi ho guardato il tuo codice, e devo essere onesto, mi ci vorrà un bel po 'di più per entrare nel tuo stato d'animo e codice quindi sono disposto a inserirmi. Ma posso suggerire un modo alternativo di dividere i sotto-problemi che penso sarà più facile da capire e scrivere.

Definire una matrice 4x (n + 1). All'indice i, j l'indice j corrisponde al sotto-problema dei primi n cavalieri. L'ultimo punto è il primo ripetuto di nuovo. Le 4 posizioni dell'array corrispondono a 4 diversi casi, che corrispondono al fatto che il primo cavaliere abbia preso il suo dolce o meno, e se il cavaliere jth abbia preso il suo dessert.

Il caso base è facile da fare perché abbiamo limitato o meno il primo cavaliere al dessert. Quindi è ancora più banale del solito. Per risolvere il caso corrente in termini di casi precedenti è abbastanza semplice: i casi in cui il primo cavaliere fa o non ottiene il dessert sono completamente separati. Per ogni caso, il valore per il caso in cui il cavaliere corrente ottiene il dessert è il minimo delle voci precedenti, più il costo attuale del dessert. Il caso in cui non lo fa è la somma della soluzione precedente in cui l'ultimo cavaliere ha ottenuto il dessert, più il costo attuale del dessert.

Per concludere l'algoritmo: tra le 4 righe, solo 2 sono rilevanti, perché solo 2 corrispondono ai casi in cui l'inizio e la fine (che è l'inizio ripetuto) sono coerenti. Prendi il più piccolo tra questi due.

Penso che il tuo algoritmo non funzioni perché la tabella è circolare. Ma possiamo risolverlo utilizzando un approccio alla programmazione dinamica diverso.

Lascia che la matrice 'C []' memorizzi i costi dei dessert di ogni cavaliere. Dobbiamo considerare due cose:

1. W [i], il costo di includere l'ith cavaliere
2. _W [i], il costo di non incluso il cavaliere, in questo caso dobbiamo includere i suoi vicini.

Dimentichiamo che il tavolo sia circolare per un po '. Mentre andiamo avanti in ogni iterazione _W [i] memorizza solo il costo di includere il vicino di sinistra di "i".

Per un particolare cavaliere 'k', possiamo calcolare W [k] e _W [k] in tempo costante usando i valori già calcolati di W [k-1] e _W [k-1].

Se non includiamo il cavaliere "k", dobbiamo includere il cavaliere "k-1" in modo che almeno uno di loro possa prendere il suo dessert. Pertanto _W [k] sarà uguale al costo di includere knight 'k-1', che è W [k-1].

Se scegliamo di includere knight "k", abbiamo due scelte, o includere "k" e "k-1" entrambi, oppure includere "k" e non "k-1". Prendiamo il minimo dei due.

Ora abbiamo:

• _W [k] = W [k-1]
• W [k] = C [k] + min (W [k-1], _ W [k-1])

Quindi, se conosciamo il valore di _W [0] e W [0], possiamo calcolare i valori W e _W per tutti i cavalieri fino a N.

Sappiamo che W [0] sarà uguale a C [0]. _W [0], il costo di non includere il cavaliere 0, sarà il costo di includere il suo vicino di sinistra che, se torniamo al problema originale è C [N-1].

Ma cosa succederà se W [1] viene scelto come _W [0] + C [1] dove _W [0] è C [N-1]? Potremmo considerare il cavaliere N-1 due volte.
Per superare questo problema controlliamo se C [N-1] < C [0], se è allora sappiamo che verrà scelto il cavaliere N-1 in modo da diminuire N di uno e quindi eliminare l'ultimo cavaliere.

La risposta finale sarà il minimo di W [N-1] e _W [N-1]

Se ti serve lo pseudocodice:

 W[0] = C[0]
_W[0] = C[N-1]

   if C[N-1] < C[0]:
         then N = N-1

   for i from 1 to N-1:
       W[i] = C[i] + min(W[i-1],_W[i-1])
       _W[i] = W[i-1]


   return min(W[N-1],_W[N-1])

Mentre fai una quantità costante di tempo in ciascuna iterazione, la complessità temporale è O (N), che andrà bene entro i limiti di tempo del tuo problema.