È questo problema NP-hard?

Question

Sto cercando di venire con un algoritmo ragionevole per questo problema:

esempio di farvi avere un po 'di palle. Ogni palla ha almeno un colore, ma può anche essere multicolore. Ogni palla ha anche un numero su di esso. Ci sono anche un sacco di scatole, che sono ciascuna un solo colore. L'obiettivo è quello di massimizzare la somma dei numeri sulle palle nelle caselle, e le uniche regole sono:

• in modo da mettere una palla in una scatola, è di avere almeno il colore della scatola su di esso
• si può solo mettere una palla in ogni di dialogo.

Per esempio, si può mettere una palla blu e verde in una scatola blu o una casella verde, ma non in una scatola rossa.

Sono venuto su con un paio di ottimizzazioni che aiutano molto in termini di tempo di esecuzione. Ad esempio, è possibile ordinare le palle in ordine di valore decrescente punto. Poi, come si va dal più alto numero al più basso, se la palla ha un solo colore, e non ci sono altre palline più alto punto che contengono quel colore, si può mettere in quella scatola (e quindi rimuovere quella scatola e che palla dal rimanenti combinazioni).

Sono solo curioso è che c'è qualche tipo di algoritmo dinamico per questo tipo di problema, o se è solo il problema del commesso viaggiatore in incognito. Sarebbe utile se sapevo che c'erano al massimo i colori di X? Qualsiasi aiuto è molto apprezzato. Grazie!

---

Modifica - qui è un semplice esempio:

Balls:

• 1 palla rossa - 5 punti
• 1 palla blu - 3 punti
• 1 verde / rosso sfera - 2 punti
• 1 verde / blu sfera - 4 punti
• 1 rosso / blu sfera - 1 punto

Scatole:

• 1 rossa
• 1 blu
• 1 verde

soluzione ottimale:

• palla rossa in casella rossa
• sfera blu in scatola blu

• verde / blu palla in scatola verde

  Valore complessivo: 12 punti (5 + 3 + 4)

Answer 1

Questo è un caso speciale della massimo problema di peso corrispondente su una pesata bilaterale grafico . Costruzione di un grafico cui vertici sinistra conforme a sfere, il cui vertici destra conforme a caselle e con il bordo di giunzione una palla e un peso scatola avente V dove V è il numero sulla palla se la sfera può essere posizionato all'interno del quadro, e 0 altrimenti . Aggiungere scatole extra o palle uniti verso l'altro lato con i bordi di peso pari a zero fino ad avere lo stesso numero di vertici su ogni lato. L'assegnazione che stai cercando è determinato dalla serie di bordi di peso diverso da zero in abbinamento massimo (totale) peso nel grafico risultante.

L'algoritmo di assegnazione può essere risolto in O (n ^ 3), dove n è qui il massimo numero di palline o scatole, utilizzando il ungherese algoritmo . (A proposito, dovrei fare il disclaimer che ho citato solo l'algoritmo ungherese, perché è il risultato teorico mi capita di conoscere e risponde presumibilmente alla domanda nel titolo se il problema originale è NP-difficile. Non ho idea se è il miglior algoritmo per l'uso nella pratica).

Answer 2

Hai provato un ALG avidi? Ordina per punti / valore e il luogo in scatola, se possibile. Se ci sono delle eccezioni ID IM come mancare di vederli.