come posso scrivere un codice Java che risolve questo problema usando un algoritmo di design?

il problema:

si sta andando su un lungo viaggio. si inizia sulla strada al miglio post 0. lungo la strada ci sono n alberghi, numerati come 1 ≤ i ≤ n, a miglio posti un 1 & lt; un 2 & lt;. …. …. & lt; un n, dove ogni a i è misurato dal punto di partenza. gli unici posti dove ti è permesso di fermarti sono in questi hotel, ma puoi scegliere a quale degli hotel ti fermi. è necessario fermarsi presso l’hotel finale (a distanza a n), che è la vostra destinazione. si vorrebbe viaggiare 200 miglia al giorno, ma questo potrebbe non essere possibile (a seconda della spaziatura degli alberghi). se viaggiate x miglia durante un giorno, la pena per quel giorno è (200 − x) 2. vuoi pianificare il tuo viaggio in modo da minimizzare la penale totale, la somma, nel corso di tutti i giorni di viaggio, delle sanzioni giornaliere.

qualcuno sa come posso scrivere un codice Java che risolve questo problema utilizzando un algoritmo avido?

quello che ho già è:

public static void greedy(int[] a) {
    int[] hotel = a;
    int[] cost = new int[hotel.length];
    int[] stop = new int[hotel.length];

    int dist = 0;

    for (int i = 0; i < hotel.length - 1; i++) {
        dist = a[i + 1] - a[i];
        cost[i] = (int) (Math.pow((200 - hotel[i]), 2));
        stop[i] = 0;
    }
}

ma non so dove andare da qui..

EN From: How can I write a Java code that solves this problem by using a design a greedy algorithm?

More similar articles:

3 Comments

  1. questa domanda di programmazione assomiglia ad un esercitazione della scuola; siete incoraggiati a provare duro da lei ovviamente… comunque, qui sono alcuni suggerimenti.


    occorre innanzitutto scegliere un algoritmo avido, cioè un algoritmo basato su una sorta di euristica che ci permette di “ottimizzare” il costo totale, basato su una scelta localmente ottimale dell’hotel successivo (la scelta da effettuare ad ogni passo).

    quindi abbiamo bisogno di dare una regola, applicabile ad ogni passo, che ci permette di scegliere l’hotel successivo.

    come scelta ottimale locale: potremmo scegliere che ogni giorno andiamo avanti, e se partiamo dal punto x, ci fermiamo al prossimo hotel più vicino al punto x+200.

    in una sorta di pseudo codice:

    //start from 0
    cost=0
    position=0
    while(position<end)
        //find the next best hotel h (based on the rule above)
        h=...
        //compute the daily_cost
        daily_cost=(h-position)^2
        //move to the selected hotel
        position=h
        //and increase the total cost:
        total_cost=total_cost+daily_cost

    quando position=end: siamo arrivati, e abbiamo calcolato il total_cost basato su questo algoritmo avido.

  2. la distanza totale che è necessario coprire è a(n), per quanto ho potuto capire. siccome dobbiamo rimanere nell’ultimo albergo, allora vorrei proporre una soluzione golosa in modo inverso.

    se a(n) - a(n-1) non può essere maggiore di 200 miglia. quindi vorrei scegliere un hotel a(i) che si trova nel bel mezzo di un posto tra a(n) e a(n) - 200. ora, come stiamo considerando un approccio avido, è necessario scegliere quell’hotel e salvare questo hotel nella vostra lista delle visite.

    ora, andare avanti da lì e scegliere il prossimo hotel dove la distanza è tra a(i) e a(i) - 200 e così via fino a raggiungere il punto di partenza.

    non sto scrivendo alcun codice come presumo che questo è compiti a casa. tuttavia, penso che si ottiene l’idea. speranza che aiuta! buona fortuna.

  3. non arare avanti e iniziare a codificare subito: iniziare con l’analisi del compito

    mezzi avidi prendere il miglior passo successivo possibile (mai guardare indietro; look-ahead limitato o non consentito).
    let dₓ be the distance for day x , and have a look at hotels at 150 , 200 , 250 miles :
    – if cost was 200-dₓ ,
    total cost is 150 with a first distance of 200 as well as with 150
    – if cost was ( 200-dₓ ) ² ,
    total cost is 22500 with a first distance of 200 , only 12500 with 150 :
    you 're best off witheach absolute difference as close to all others as possible
    – without ( full ) look-ahead , you don 'tknowall remaining :
    next difference as close toexpected average remainingas possible
    – all other things being equal , you 're better off with fewer day trips than with more
    – with a look-ahead of 1 , the single-day trip with cost 50 and 2500 becomes an option .


    how I can write a Java code that solves this problem?
    con avido rivisitato e uno (più) esempio considerato (stesso come sempre):

    • non scrivere un algoritmo (ancora):

    • se
      non in analisi, questo è dove i problemi con la definizione del compito sono tenuti a diventare evidente: è 200 miles un limite superiore? (posso cambiare direzione?)
      codificare un test, farlo controllare le attività di esempio e risultati. fatelo contrassegnare i risultati errati (solo).
    • solo allora iniziare a disegnare una soluzione.

      abitualmente, prendo una deviazione / scorciatoia qui: avvio un file sorgente (o continuo quello con i test) e metto giù una descrizione del compito da compiere usando la convenzione di documentazione dello strumento di programmazione preferito, con Java, che sarebbe doc comments.
      abbozzo la soluzione, sintatticamente come commenti in una forma facilmente divisa (Java: // line comments)

    • controllare la soluzione abbozzata: qualsiasi semplificazione si suggerisce?
      se sembra complesso: le restrizioni possono essere eliminate per consentire un approccio più semplice dare gli stessi risultati?
      si può risparmiare tempo, alla fine di attuare tale approccio prima, anche se rivedere le restrizioni è sceso risultati nel rifiuto come soluzione.
      (qui, il suggerimento di Daniele valeva la pena di provare se il vostro approccio sembrava significativamente più complesso.)
    • con una descrizione sostenibile di cosa fare, sei pronto a codificare

Leave a Reply

Your email address will not be published. Required fields are marked *