Algoritmo di distribuzione dei semi con complessità migliore di O (n ^ 3)?

2

Ho incluso il mio approccio e la mia soluzione. La mia soluzione funziona bene, tuttavia, non è ottimizzata con la complessità di O (n ^ 3)

Un ONG sta eseguendo un programma di distribuzione dei semi. Ha una quantità limitata di semi di qualità varia. Per ottenere i semi, l'agricoltore deve richiedere il numero di semi. La distribuzione dei semi avviene solo di domenica con l'obiettivo che i massimi agricoltori ottengano i semi della migliore qualità dello stesso tipo.

Considera che le ONG hanno seguito i semi e contano (ordinati per qualità - il livello più alto è il più alto):

|Quality|Fruit1|Fruit2|Fruit3|
|-------|------|------|------|
|Highest|     3|     3|     1|
|Medium |     2|     0|     0|
|Low    |     4|     0|     0|

Semi obbligatori:

  • Farmer 1: 2
  • Farmer 2: 3
  • Farmer 3: 1
  • Farmer 4: 2
  • Farmer 5: 3

Output: l'obiettivo è assegnare le sementi di massima qualità ai massimi agricoltori.

  • Farmer 1: Highest Fruit1
  • Farmer 2: Highest - Fruit2
  • Farmer 3: Highest - Fruit1
  • Farmer 4: Medium - Fruit1
  • Farmer 5: Low - Fruit1

Qui, i contadini 1 e 3 in combinazione hanno richiesto 3 semi, quindi, in combinazione, hanno ottenuto il frutto più alto1.

Il mio approccio (Pseudocode)

Ho le seguenti classi di dominio: Farmer, QualityType, FruitType, Seeds

QualityType ha un elenco di FruitType che contiene un elenco di semi.

Per ottenere il risultato, sto seguendo il seguente:

  • Esegui l'iter dal più alto tipo di qualità al più basso.
  • esegui l'iterazione annidata al tipo di frutta e ai semi.
  • Per ogni seme, controlla se abbiamo farmer1 che chiede lo stesso numero di semi - da solo o in combinazione con qualcun altro.
  • Se non ti sposti con il contadino due.
  • Questo funziona tuttavia non è ottimizzato in quanto ha 3 cicli annidati.

Puoi suggerire qualsiasi algoritmo in grado di semplificarlo?

    
posta JohncyWhack 09.07.2015 - 16:28
fonte

1 risposta

1

Il modo migliore è dividere prima lo spazio problematico, quindi devi solo considerare quanti agricoltori vogliono quanti semi di un particolare tipo e qualità di frutta. Puoi farlo in una singola iterazione. Devi sapere quanti tipi di frutta e seme sono richiesti.

Quindi dividi il numero di semi di ciascuna qualità per il numero desiderato, arrotondando per difetto e assegnando il resto assegnando 1 al numero limitato di agricoltori. Puoi ottimizzarlo determinando il resto come frazione e dando il seme in più a quella frazione di agricoltori (ad esempio 7 semi, 4 agricoltori = 1 1/3 seme ciascuno, il che significa che un agricoltore ottiene 1 in meno di quello che ha chiesto più un extra 1 se il contatore del contadino < = 7% 4 (anche se questo si rompe se la frazione è inferiore a 1 per esempio 4 semi, 7 richiesti, nel qual caso ogni agricoltore ottiene inizialmente 0 semi, il resto è ancora assegnato come prima)

Questo rende 2 iterazioni: 1 per costruire il set di requisiti degli agricoltori e un altro per soddisfarli.

    
risposta data 09.07.2015 - 17:01
fonte

Leggi altre domande sui tag