algoritmo zaino con una proprietà aggiuntiva

Question

Quando c'è 1 proprietà, io capisco quello che sta succedendo in là. Sto riscontrando un problema con la comprensione del problema dello zaino quando c'è più di una proprietà.

devo scrivere un programma che utilizza l'algoritmo zaino con un 2 proprietà. Il Maestro ci ha detto che deve essere fatto in un array 3d. Non riesco a immaginare come apparirebbe un simile array.

Diciamo che qui è il mio ingresso:

4 3 4 // number of records below, 1st property of backpack, 2nd property of backpack 
1 1 1 // 1st property, 2nd property, cost 
1 2 2 // 1st property, 2nd property, cost 
2 3 3 // 1st property, 2nd property, cost 
3 4 5 // 1st property, 2nd property, cost 

E l'uscita sarebbe quella faccia:

4 // the cheapest sum of costs of 2 records 
1 3 // numbers of these 2 records 

La spiegazione di uscita: 2 set di record FIT in linea 1'st dell'input :

(1) - numero di registrazione 1 e numero di registrazione 3

1 1 1 
+ 2 3 3 
------- 
    3 4 4 

(2) - numero record 4

3 4 5 

Perché 1 ° set dei record è il più economico (4 < 5), abbiamo scelto. Non solo dovrò scoprire se esiste una tale serie di record, ma dovrò anche trovare i record che ho riassunto.

Ma per ora, ho solo bisogno di capire, come potrà 3d matrice simile. Qualcuno di voi potrebbe aiutarmi e mostrarlo, strato per strato, proprio come nella mia immagine, come sarebbe? Grazie.

Answer 1

Si sta cercando di fare qualcosa di impossibile - questo è il vostro problema.

Quando si aggiunge al numero di dimensioni, i tuoi articoli sono sempre proprietà aggiuntive. Così, invece di una sinistra, lato colonna di una tabella (prop1), si ha lato rettangolo (prop1 x prop2) o sul lato del blocco (prop1 x prop2 x prop3) e così via. Ma i vincoli esistenti, che definiscono il lato superiore della riga della tabella, dovrebbero avere lo stesso numero di dimensioni. Non solo una dimensione!. Quindi, si mai essere in grado di mettere problema dei due proprietà in un blocco di 3-dimensionale, è necessario invece blocco 4D. Blocco 6D per 3 proprietà e così via.

Answer 2

Dire che si sta utilizzando una tabella tridimensionale: A[x][y][z]=k, x: somma 1a proprietà; y: somma 2a proprietà; z: somma 3a proprietà; k: costo minimo (premio massimo, che io preferisco usare ricompensa)

Così si iterare elementi. Di 'elemento corrente è (p1, p2, p3, ricompensa) (ricompensa = - Costo).per ogni (x,y,z,k), la formula di aggiornamento:

A[x+p1][y+p2][z+p3] = max(A[x+p1][y+p2][z+p3], A[x+p1][y+p2][z+p3] + reward) 

Se il primo termine sul lato destro è maggiore, su slot A[x+p1][y+p2][z+p3], la configurazione di zaino è rimanere fermi; in caso contrario, si aggiorna lo zaino con quello di A[x+p1][y+p2][z+p3] più l'elemento corrente.

Spero che questo chiarisca le cose.