Ridurre al minimo l'uso della carta

Question

Ridurre al minimo l'uso della carta

#1 da (1 voti)

1

Recentemente ho affrontato questo problema in un curriculum di programmazione dinamica e onestamente non ho idea di come determinare lo stato appropriato.

Hai dati di N (1 < = N < = 70) e M (1 < = M < = N). Ogni paragrafo i richiede PL_i (1 < = PL_i < = 100) linee e riferimenti al massimo una cifra. Ogni figura è riferita esattamente una volta (cioè, non ci sono due paragrafi che possono fare riferimento alla stessa figura, e per ogni figura c'è un paragrafo che fa riferimento a essa). Ogni figura richiede PF_i (1 < = PF_i < = 100) righe.

Il compito è di distribuire quelle figure e paragrafi sulla carta nell'ordine in cui sono dati, dove una carta si adatta al massimo per le linee L . Nessun paragrafo o figura è troppo grande per stare su un foglio. Se un paragrafo x posto su carta x_p fa riferimento a una figura y allora y deve essere posizionato su entrambi i fogli < strong> x_p - 1 o x_p o x_p + 1 .

Dobbiamo trovare il numero minimo di righe (e quindi di pagine) da allocare per distribuire tutte le figure e i paragrafi. Qualsiasi aiuto sarebbe estremamente apprezzato. Grazie in anticipo!

algorithms optimization dynamic-programming

posta Chris 30.06.2012 - 11:51

fonte

1 risposta

Leggi altre domande sui tag algorithms optimization dynamic-programming

API Contour Mapping Distribuzione TFS non cronologica?

score 1 · Answer 1

Avere una matrice 2d. La riga è il numero del numero di paragrafi che puoi adattare, la colonna è il numero di cifre che puoi adattare, il valore della cella è il numero minimo di linee possibili. Cella [0,0] = 0. Cella [1,0] e Cella [0,1] possono essere calcolate banalmente. La cella [1,1] può essere calcolata trovando un minimo basato su cella [1,0] e cella [0,1]. La cella in basso a destra è la tua risposta. C'è un passo mancante in questa spiegazione relativa a "x_p - 1 o x_p o x_p + 1", ma penso che questa sia probabilmente la direzione giusta per usare la programmazione dinamica per risolvere questo problema.

Ulteriori dettagli:
Puoi calcolare Cell [X, Y] trovando il modo più efficiente per raggiungerlo (ad esempio, controlla il costo minimo per raggiungerlo dalla cella [X-1, Y] e dalla cella [X, Y-1]). Nel caso di una figura, il costo per saltare una cella non sarà necessariamente uguale al numero di linee nella figura, poiché potresti essere costretto a spostare la figura nella pagina successiva. Ciò che manca a questa spiegazione è come tagliare le celle dove le cifre sono molto indietro o davanti ai paragrafi.