Newsgroup: it.scienza.informatica
Titolo: Come risolvereste questo problema?

1 - Fisso un insieme di numeri interi (per esempio 40,41,42,43)
2 - Dico che A è composto da 1 numero 40, da 2 numeri 41, da 2 numeri 
42, da 1 numero 43
2 - Dico che B è composto da 1 numero 40, da 2 numeri 41, da 1 numero 42
2 - Dico che C è composto da 1 numero 41, da 2 numeri 42, da 1 numero 43
In altri termini ho:
   40  41  42  43
A  1   2   2   1
B  1   2   1
C      1   2   1
A questo punto immaginiamo di avere a disposizione 5 numeri 40, 8 numeri 
  41, 8 numeri 42 e 5 numeri 43 (una specie di termine noto)
Ossia:
40 41 42 43
  5  8  8  5
Il problema è trovare quanti A, B e C posso avere tali per cui siano 
MINIMI i numeri che rimangono fuori dalla selezione. Per esempio se 
scelgo 1 di A, 1 di B ed 1 di C avrò che:
              40 41 42 43                40 41 42 43
  A +  B +  C  2  5  5  2 e mi rimangono  3  3  3  3 = 12 numeri fuori
2A +  B +  C  3  7  7  3 e mi rimangono  2  1  1  2 =  6 numeri fuori
  A + 2B +  C  3  7  6  2 e mi rimangono  2  1  2  3 =  8 numeri fuori
  A +  B + 2C  2  6  7  3 e mi rimangono  3  2  1  2 =  8 numeri fuori
  A +  B + 2C  2  6  7  3 e mi rimangono  3  2  1  2 =  8 numeri fuori
...   ...   ...   ...   ...   ...   ...   ...   ...   ...   ...   ...
4A + 0B + 0C  4  8  8  4 e mi rimangono  1  0  0  1 =  2 numeri fuori
eccetera
Per un caso così semplice la soluzione migliore sembra essere 4A perchè 
mi lascia fuori dagli iniziali 5 8 8 5 solo 1 numero 40 ed un numero 43.
Ma per casi più complessi come si può fare? Voi che approccio 
seguireste? Di quale tipologia di algoritmi fareste uso?
Giovanni.



Sembra un problema di ottimizzazione lineare risolvibile con l'algoritmo
del simplesso dove la funzione da ottimizzare e` a*N_a, b*N_b, c*N_c,...,
dove a,b,c.. sono i numeri di ogni insieme e N_a,N_b,N_c,... sono il
totale dei numeri contenuti negli stessi.
Ma non sono sicuro che sia il migliore perche` A MIO AVVISO il metodo
migliore e`:
a,b,c,d,... sono i vettori di "numeri di ogni numero"
rispettivi ad ogni insieme; m e` il vettore di "massimo
numero di ogni numero".
trova il massimo tra <a,m> , <b,m> , <c,m>,.... (prodotti scalari) e
di quello eletto, supponiamo b, trova il minimo rapporto tra m1/b1,
m2/b2,.... dove mN e` il numero di numeri dell'N-esimo numero per m mentre
aN e` il(....).
Il rapporto trovato e arrotondato per difetto e` il numero di insmiemi "b"
che ottimizza lo riempimento. Complessita`: O(3N) (economico no?).
Ripeto: e` il migliore A MIO AVVISO.
Ciao.


Mi sembra un'estensione del problema knapsack (anzi, subset-sum), per 
cui probabilmente il metodo piu` efficiente e` Integer Linear Programming.
Nell'esempio, puoi scrivere delle (dis)equazioni lineari tipo:
1A + 1B <= 5		(quantita` di 40)
2A + 2B + C <= 8	(quantita` di 41)
2A + B + 2C <= 8	(quantita` di 42)
A + C <= 5		(quantita` di 43)
Poi devi mettere una funzione obiettivo. Forse la cosa piu` seplice e` 
inserire delle slack variables S1, ..., S4, una per ciascuna 
disuguaglianza. Quindi riscrivi le disequazioni come equazioni:
1A + 1B + S1 <= 5	(quantita` di 40)
2A + 2B + C +S2 <= 8	(quantita` di 41)
2A + B + 2C +S3 <= 8	(quantita` di 42)
A + C + S4 <= 5		(quantita` di 43)
e poi minimizzi la somma delle slack: min(S1+S2+S3+S4).
Infine, imponi che tutte le variabili siano intere e non negative.
Dai questo modello ad un risolutore ILP e dovrebbe darti la soluzione 
ottima. I risolutori piu` efficienti sono probabilmente CPLEX ed 
Xpress-MP; se ne vuoi uno gratuito c'e` GLPK.
Ciao,
Marco
--
http://www.ing.unife.it/docenti/MarcoGavanelli/