Problema di imballo dei contenitori (o dello zaino?)

Question

Ho una collezione di numeri da 43 a 50 compresi tra 0,133 e 0,005 (ma principalmente sul lato piccolo). Vorrei trovare, se possibile, tutte le combinazioni che hanno una somma tra L e R, che sono molto vicini tra loro. *

Il metodo forza bruta richiede 2 a 2 gradini, che isn è fattibile Qual è un buon metodo da usare qui?

Modifica: le combinazioni verranno utilizzate in un calcolo e scartate. (Se stai scrivendo il codice, puoi presumere che siano semplicemente in uscita, io modifico se necessario.) Il numero di combinazioni sarà presumibilmente troppo grande per essere conservato in memoria.

* L = 0,5877866649021190081897311406, R = 0,5918521703507438353981412820.

Answer 1

L'idea di base è convertirla in un problema di zaino intero (che è facile).

Scegliere un numero reale piccolo e e numeri tondi nel problema originale con quelli rappresentabili come k*e con numero intero . Più piccolo è e, più grandi saranno gli interi (compromissione dell'efficienza) ma la soluzione del problema modificato sarà più vicina a quella originale. Un e=d/(4*43) dove d è la larghezza dell'intervallo di destinazione dovrebbe essere abbastanza piccolo.

Se il problema modificato ha una soluzione esatta sommando al centro (arrotondato a e) dell'intervallo di destinazione, il problema originale ne ha uno da qualche parte nell'intervallo.

Answer 2

Non ci hai fornito informazioni sufficienti. Ma sembra che tu sia nei guai se in realtà vuoi OUTPUT ogni possibile combinazione. Ad esempio, coerente con quello che ci hai detto che ogni numero è ~ .027. Se questo è il caso, allora ogni raccolta di metà degli elementi soddisfa il tuo criterio. Ma ci sono 43 scegli 21 di questi set, il che significa che devi produrre almeno 1052049481860 set. (troppi per essere fattibili)

Certamente il tempo di esecuzione non sarà migliore della lunghezza dell'output richiesto.

Answer 3

In realtà, c'è un modo più veloce intorno a questo:

(python)

sums_possible = [(0, [])] 
# sums_possible is an array of tuples like this: (number, numbers_that_yield_this_sum_array) 
for number in numbers: 
    sums_possible_for_this_number = [] 
    for sum in sums_possible: 
     sums_possible_for_this_number.insert((number + sum[0], sum[1] + [number])) 
    sums_possible = sums_possible + sums_possible_for_this_number 

results = [sum[1] for sum in sums_possible if sum[0]>=L and sum[1]<=R] 

Inoltre, Aaron è giusto, quindi questo può o non può essere fattibile per voi