Zaino semplificato in PHP

3

Ho due casi in cui mi piacerebbe visualizzare le informazioni in un allineamento "giustificato" - ma non mi interessa se i valori sono commutati in ordine. Un esempio è la visualizzazione dei nomi utente delle persone online:

Anton Brother68 Commissar Dougheater Elflord Foobar Goop Hoo Iee Joo

Riorganizzandoli, potremmo ottenere esattamente 22 caratteri su ciascuna riga:

Anton Brother68 Foobar
Commissar Elflord Goop
Dougheater Hoo Iee Joo

Questa è una sorta di zaino, ma sembra che ci dovrebbe essere una soluzione P dato che non mi interessa la perfezione, e ho più linee.

La seconda istanza è identica, tranne che per i nomi e il conteggio dei caratteri, visualizzerei immagini casuali e useremo la loro larghezza.

    
posta Mikhail 07.07.2011 - 17:25
fonte

2 risposte

1

Decidi il numero di linee, ad esempio prendendo la lunghezza totale e dividendo per alcune dimensioni massime della linea. Ordina l'elenco dei nomi in ordine decrescente. Recupera ripetutamente il nome più lungo dall'elenco ordinato e aggiungilo alla riga più breve fino a quel momento. Dopo aver aggiunto tutti i nomi alle linee, potresti voler randomizzare l'ordine o ordinare alfabeticamente all'interno delle linee per renderlo migliore.

Questa è un'approssimazione molto vicina della soluzione ottimale.

    
risposta data 14.12.2011 - 19:10
fonte
1

Non sembra un problema con lo zaino perché l'utlity di tutte le parole piazzate è 1 (correggimi se ho torto).

Forse invece binpacking?

    
risposta data 16.08.2011 - 17:19
fonte

Leggi altre domande sui tag