Abbiamo 10 borse. Ogni borsa ha 5 compartimenti numerati da 1 a 5. Abbiamo 100 oggetti per riempire tutti i compartimenti e borse. Il numero dello scomparto x in una borsa è identico al compartimento dello stesso numero negli altri sacchetti. Mettere alcuni oggetti insieme in una borsa potrebbe essere pericoloso. Il pericolo varia da 0 a 3.
- L'inserimento di un oggetto in un compartimento ha un punteggio da 0 a 3: S_obj_o_comp_c
- L'inserimento di un oggetto in una borsa ha un valore compreso tra 0 e 3: S_obj_o_bag_b
- Mettere l'oggetto x nella stessa busta dell'oggetto y ha un costo da 0 a -3: C_obj_x_obj_y.
Il problema è come mettere gli oggetti nei compartimenti per ottenere il punteggio massimo.
Il numero di diverse combinazioni di oggetti / compartimenti / borse è 100 * 99 * ... * 50 che è 100!/49!
Chiaramente, non è possibile risolvere questo problema con Backtrack o brute-force .
È possibile trovare una soluzione esatta per questo problema? Che dire della soluzione approssimativa?