Apple problema alimentare

Question

Apple problema alimentare

#1 da (3 voti)
#2 da (0 voti)
#3 da (0 voti)

7

Il giocatore A e il giocatore B giocano una partita. Al centro del tavolo c'è una pentola piena di mele N di diverso peso. Il giocatore A inizia per primo e sceglie una mela e inizia a mangiarla. Perdere tempo nessun giocatore B fa lo stesso. Quando un giocatore mangia tutta la mela, senza perdere tempo, ripeti la stessa procedura. Nel caso in cui entrambi i giocatori abbiano mangiato la mela allo stesso tempo, il giocatore A ha ancora il vantaggio di scegliere per primo. Nota che entrambi i giocatori mangiano con la stessa velocità

Quale mela dovrebbe scegliere il giocatore A in un primo momento per assicurarti che con le giuste tattiche egli mangerà quanto più grammi di mele possibili se il giocatore B gioca in modo ottimale?

Ho pensato che scegliere la mela più piccola o più grande dovrebbe fare il lavoro, ma ci sono casi specifici in cui questo non funziona.

Questo è il problema del contest C ++, quindi dovrebbe esserci una buona soluzione a questo. Penso che la forza bruta possa fornire una soluzione, ma ciò richiederà molto tempo, perché il numero di mele è fino a 10000.

Preferirei un suggerimento su come affrontare questa domanda, come trovare la tattica o l'intuizione ottimale piuttosto che un codice.

c++ algorithms

posta Stefan4024 24.02.2014 - 01:42

fonte

3 risposte

Leggi altre domande sui tag c++ algorithms

Sono 500 milioni di righe di codice anche lontanamente possibili? [chiuso] Come modellare e memorizzare un'entità che ha "uno o più" valori

score 3 · Answer 1

Una risposta non ricorsiva: dividi le mele in due pile, in modo che siano il più vicino possibile alla pari. Quindi, mangia la mela più piccola nella pila più grande.

Dimezzare la pila è lasciata al lettore, ma ricorda che la differenza nella dimensione della pila non può essere maggiore della mela più piccola nella pila più grande; se è più grande, spostando la mela nell'altra pila otterrai una risposta più ravvicinata. Può anche non essere più grande della differenza tra una mela nella pila più grande e la mela più piccola successiva nella pila più piccola - se la pila più grande contiene una mela da 600 grammi, e la pila più piccola contiene una mela da 500 grammi, e la differenza tra le due pile è più di 100 grammi, quindi è possibile scambiare quelle due mele e avvicinarsi.

Ad esempio, se hai 300 + 400 + 500 grammi, dovresti dividerli in due pile, ognuna delle quali è il più vicino possibile a (300 + 400 + 500) / 2 = 600 grammi. Ne risulta uno di 500 grammi, l'altro 300 + 400 = 700 grammi. Mangia la mela più piccola della più grande pila (700 grammi) - vale a dire la mela da 300 grammi.

Nel caso di 100 + 200 + 300 + 900, il più vicino è possibile ottenere due pile di 750 grammi ciascuna è una pila di 900, l'altra di 600, mangiare la più grande (e unica) mela dal più grande ( 900 grammi) pila.

score 0 · Answer 2

Come è stato detto, può essere risolto tramite il backtracking. La cosa importante da notare è che il peso delle mele consumate è proporzionale al tempo trascorso a mangiare. Ciò significa che massimizzare il peso equivale a massimizzare il tempo trascorso a mangiare.

Un'altra osservazione è che non è mai utile fermarsi a mangiare. Ciò significa che le pause possono essere ignorate.

Quindi l'algoritmo che propongo:

definisce stato come:

importo consumato da A
importo consumato da B
elenco di mele rimaste

Ora in ogni fase del backtracking ricevi questo stato . La persona a sua volta che sceglie un'altra mela è quella con la quantità minore consumata (perché ha mangiato più velocemente). Ora è facile generare un altro stato per l'algoritmo di backtracking.

Esempio

supponi di aver ricevuto lo stato:

mangiato da A = 600
mangiato da B = 400
mele sinistra = 300, 400

Da questo puoi generare stati:

mangiato da A = 600
mangiato da B = 700
mele sinistra = 400

e

mangiato da A = 600
mangiato da B = 800
mele sinistra = 300

fine dell'esempio

L'algoritmo termina quando non ci sono più mele nella lista. Probabilmente sarà necessario pensare ad alcune euristiche (l'ordine in cui le mele vengono raccolte). Puoi anche ridurre considerevolmente lo spazio di ricerca se mantieni la somma delle mele rimaste e finisci quando è chiaro che non puoi essere migliore di una soluzione che hai trovato prima. Sono sicuro che ci sono altre possibilità simili su come accelerarlo.

score 0 · Answer 3

Non ne so molto di "nodi" e "grafici", e inoltre, preferisco un approccio pratico ....

Questo è quello che ho deciso; è un approccio a forza bruta ed è un compromesso tra tempo di CPU e tempo del programmatore (il tempo di CPU è più economico). Funziona bene con un piccolo numero di mele; 9 mele impiegano 3,5 secondi per correre, 10 mele impiegano circa 40 secondi; più di 12 probabilmente vorrebbe un approccio diverso.

Scrivi una funzione che richiede (tempo finora per il giocatore 1, tempo finora per il giocatore 2, la prossima mela e le mele rimanenti). Ritorna, per il gioco ottimale sia per il giocatore 1 che per il giocatore 2: la quantità di mela mangiata dal giocatore 1, la quantità di mela mangiata dal giocatore 2 e, in ordine, le mele mangiate.

Il codice per questa funzione è il seguente:

La "prossima mela" viene mangiata (aggiunta al tempo del giocatore 1 o del giocatore 2, a seconda di chi è il prossimo a causa del consumo di una mela).

Se non ci sono (più) mele, questa funzione è ora banale - restituisci i tempi per il giocatore 1 e il giocatore 2 (che hai già calcolato) e l'elenco delle mele mangiate (che consiste nella "prossima mela a essere mangiato ").

Altrimenti, esamina ciascuna mela della lista una ad una (di seguito la nuova "prossima mela"), effettuando le seguenti operazioni: chiama questa stessa funzione, con i tempi aggiornati, la nuova "prossima mela" e l'elenco di mele restanti. Ottieni il risultato di ciascuno, e trova quello con il tempo più basso per il giocatore 1, o il tempo più basso per il giocatore 2, a seconda di chi sta scegliendo questa mela. Poiché il tempo di ritorno per il giocatore 1 + giocatore 2 deve essere uguale a quello delle mele, il tempo più basso per il giocatore 1 = il tempo più alto per il giocatore 2, quindi puoi facilmente ordinare l'elenco per durata per il giocatore 1, e poi prendere la prima o l'ultima voce nell'elenco dei risultati. Qualunque sia la voce selezionata, aggiungi la tua "prossima mela" all'inizio della "lista di ordinazioni mangiate di mele" (il terzo elemento del risultato) e restituisci il risultato.

Si noti che potrebbero esserci più risultati "migliori". Quando in realtà stai chiamando questa funzione per davvero, imposta il "tempo finora" per il giocatore 1 & Da 2 a 0 e imposta la prima "mela succes- siva" su 0 - una mela immaginaria, quindi non dobbiamo sapere in anticipo quale mela da mangiare per prima.