Ho un set S di size n i cui membri hanno associato a loro un numero nell'intervallo 0.00 a 1.00 inclusive.
Voglio selezionare un sottoinsieme T di size m con questa proprietà:
- la media dei numeri associati ai membri di
Tdeve essere compresa nell'intervallo specificato daxay(ad esempio0.65a0.75). Espressa in modo diverso: la somma dei numeri associati ai membri diTdeve rientrare in un intervallo specificato (ad esempio,0.65msu0.75m)
Inoltre, tra tutti i possibili T s per un dato S , x , y , voglio sceglierne uno (uniformemente) a caso.
Il mio metodo attuale consiste nel selezionare casualmente m membri di S , quindi verificare se la somma rientra nell'intervallo desiderato. Ripeto finché non ottengo un risultato soddisfacente. Esiste un algoritmo (possibilmente programmazione dinamica?) Per ottenere il sottoinsieme desiderato senza usare guess e check?
Esempio:
S è un insieme di domande n = 200 , a ognuna assegnata una valutazione di difficoltà tra 0 e 1 inclusive. Voglio generare un test T con m = 50 domande dove la difficoltà media è tra 0.65 e 0.75 inclusive. Inoltre voglio selezionare un (uniformemente) casuale T , tra tutti i possibili T che soddisfano le mie condizioni.
Un altro esempio:
S = {0.1, 0.3, 0.5, 0.8, 1.0}
n = 5
m = 3
x = 0.5
y = 0.75
All possible T and their average value
{0.1, 0.3, 0.5} = 0.8 / 3 = 0.26
{0.1, 0.3, 0.8} = 1.2 / 3 = 0.40
{0.1, 0.3, 1.0} = 1.4 / 3 = 0.46
{0.1, 0.5, 0.8} = 1.4 / 3 = 0.46
{0.1, 0.5, 1.0} = 1.6 / 3 = 0.53
{0.1, 0.8, 1.0} = 1.9 / 3 = 0.63
{0.3, 0.5, 0.8} = 1.6 / 3 = 0.53
{0.3, 0.5, 1.0} = 1.8 / 3 = 0.60
{0.3, 0.8, 1.0} = 2.1 / 3 = 0.70
{0.5, 0.8, 1.0} = 2.3 / 3 = 0.76
Subsets of S with size m with average values between x and y
{0.1, 0.5, 1.0}
{0.1, 0.8, 1.0}
{0.3, 0.5, 0.8}
{0.3, 0.5, 1.0}
{0.3, 0.8, 1.0}
Sto cercando di trovare un algoritmo per produrre uno di questi 5 sottoinsiemi a caso, senza prima calcolare ogni sottoinsieme di S con dimensione m. Sembra che l'ipotesi e il controllo siano il metodo migliore.