Algoritmo efficiente per trovare un insieme di numeri in un intervallo

Per cercare un "punto debole" come questo, generalmente usi una coda di priorità. L'idea è che hai una lista ordinata secondo un requisito specifico. Più una soluzione è simile a un requisito, più è probabile che verrà scelto dalla coda di priorità per cercare più soluzioni.

In questo caso, la tua soluzione sarebbe una serie di indici in cui ciascuno appartiene a un numero nell'array. Quindi in altre parole per la soluzione 2 * 7, avresti un array [1,2]. Puoi anche usare un numero binario con n bit se preferisci. La coda di priorità, al fine di determinare quale sia la migliore, dovrebbe moltiplicare tutti i numeri riferiti dagli indici insieme. Il punto debole in questo caso sarà il luogo in cui è probabile trovare la maggior parte delle soluzioni, quindi in questo caso sarebbe la media tra il massimo e il minimo, 1750.

L'algoritmo è il seguente:

Aggiungi ciascun numero nel proprio array di soluzioni e aggiungilo alla coda di priorità.

Quindi, a partire dal primo (il più vicino a (massimo + minimo) / 2), rimuoverlo dalla coda di priorità e per ogni indice non incluso nella soluzione, aggiungerlo alla soluzione e reinserirlo nella coda di priorità.

Se si riscontra che il tempo corrente del prodotto ogni nuovo numero supera il massimo, non lo si aggiunge nemmeno alla coda. Se è inferiore al minimo, non fai nulla con esso.

Se è nel minimo e nel massimo, fai qualcosa con esso.

Continua finché non li hai tutti.

In questo modo, stai riducendo la ricerca di soluzioni per valori vicini alla tua media. Dovresti ottenere la maggior parte delle tue soluzioni immediatamente in questo modo, ma per ottenerle tutte, dovrai cercare nell'intero spazio della soluzione 2 ^ n-1.

Consente di eseguire un test rapido per una piccola gamma di valori [1,2,3,4]. Voglio trovare tutte le soluzioni i cui valori sono compresi tra 10 e 12, quindi prima aggiungerei tutti i numeri nella loro soluzione e inserirli nella coda di priorità. La priorità sarebbe quindi: [[4], [3], [2], [1]].

Prendo il primo [4] e aggiungo 3, 2 e 1 nelle proprie soluzioni e lo aggiungo alla coda di priorità. La coda di priorità diventa quindi:

[[4, 3], [4, 2], [4, 1], [4], [3], [2], [1]]

Vedo che ho già ottenuto il mio primo valore [4, 3]! Continuiamo e vediamo cosa succede:

[[4, 3, 1], [4, 2], [4, 1], [4], [3], [2], [1]]

Si noti che [4, 3, 2] era troppo grande e non è stato aggiunto. Ho trovato un'altra soluzione [4, 3, 1] !

Se qualcosa non è chiaro chiedi e proverò a chiarire.

Spero che ti aiuti.

La soluzione di forza bruta a questo problema dovrebbe richiedere solo pochi secondi su una CPU moderna, dato che ci sono solo circa un milione di numeri da controllare. Ma sarebbe troppo facile.

Suppongo che ogni prodotto contenga ogni intero una sola volta. [Non hai detto.]

Assegna una pila di numeri interi. TOS è il valore più alto. P è il prodotto di interi nello stack.

Sarebbe possibile ignorare il numero 1. Potrebbe essere banalmente aggiunto alla fine se necessario, ma perché preoccuparsi? Pseudocodice:

Push 1 on the stack.
Forever do
  If P > 1000 and P < 2500
    Found one: save stack contents
  If TOS == 20
    Pop while TOS == 20
    End if stack is empty
    Increment TOS
  Elsif P >= 2500
    Pop
    Increment TOS
  Else 
    Push TOS+1

Sembra che dovrebbe funzionare (presupponendo di aver compreso correttamente il problema). Lascio il codice come esercizio.