Algoritmo dello zaino con 2 proprietà. Come implementarlo in un array 3d?

Question

Sto riscontrando un problema con la comprensione del problema dello zaino quando c'è più di una proprietà. Quando c'è 1 proprietà,

Devo scrivere un programma che utilizza l'algoritmo dello zaino con 2 proprietà. Il Maestro ci ha detto che deve essere fatto in un array 3d. L'implementazione errata porterà a O (2^n) tempo di elaborazione. 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) - il numero 1 e registrare record di numero 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 apparirà l'array 3d. Qualcuno di voi potrebbe aiutarmi e mostrarlo, strato per strato, proprio come nella mia immagine, come sarebbe? Grazie.

Answer 1

Stai cercando di fare qualcosa di impossibile - questo è il tuo problema.

Quando si aggiunge al numero di dimensioni, gli elementi acquisiscono proprietà aggiuntive. Quindi, invece di un lato sinistro della colonna di un tavolo (prop1), hai il lato del rettangolo (prop1 x prop2) o il 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, non sarà mai essere in grado di mettere il problema di due proprietà in un blocco tridimensionale, hai invece bisogno del blocco 4D. Blocco 6D per 3 proprietà e così via.

Answer 2

Per convertire dall'algoritmo alla risoluzione del problema dello zaino con 1-vincolo con la programmazione dinamica, risolvere il problema dei 2 vincoli è molto semplice. Per qualcuno, per disegnare un'immagine 3d che mostri cosa sta succedendo lì, immagino sia un po 'difficile. L'algoritmo, d'altro canto, è abbastanza semplice:

Suppongo che tu voglia una soluzione esatta, e che tu voglia minimizzare i costi, non massimizzare il valore (che ho ricavato dal tuo esempio). Non ho mai fatto nessuna di queste varianti, quindi non posso garantire che non ci sia un errore.

1-vincolo

La matrice per la 1-vincolo problema dello zaino è (item x weight) memorizzare il valore in ciascuna posizione.

L'algoritmo è fondamentalmente:

// WL = backpack weight limit 
A[0, 0] = 0 
for w = 1, 2, ..., WL // weight 
    A[0, w] = INFINITY 
for i = 1, 2, ..., n // items 
    for w = 0, 1, ..., WL // weight 
    // wi and ci are the weight and cost of the item respectively 
    // A[i-1, w-wi] + ci = 0 when wi > w 
    A[i, w] = min(A[i-1, w], A[i-1, w-wi] + ci) 

2-vincolo

Ora per estendere questo al includere un altro vincolo è solo: (diciamo size è l'altro vincolo)

La matrice sarebbe (item x weight x size).

// WL = backpack weight limit 
// SL = backpack size limit 
for w = 0, 1, ..., WL // weight 
    for s = 0, 1, ..., SL // size 
    A[0, w, s] = INFINITY 
A[0, 0, 0] = 0 
for i = 1, 2, ..., n // items 
    for w = 0, 1, ..., WL // weight 
    for s = 0, 1, ..., SL // size 
     // wi, si and ci are the weight, size and cost of the item respectively 
     // A[i-1, w-wi, s-si] + ci = 0 when wi > w or si > s 
     A[i, w, s] = min(A[i-1, w, s], A[i-1, w-wi, s-si] + ci)