Come posso determinare se un determinato numero può essere composto da un insieme di numeri?

Question

Quindi ho un numero intero, ad es. 1234567890 e un determinato insieme di numeri, ad es. {4, 7, 18, 32, 57, 68}

La domanda è se 1234567890 può essere composto dai numeri indicati (è possibile utilizzare un numero più di una volta e non è necessario utilizzare tutto loro). Nel caso di cui sopra, una soluzione è:
38580246 * + 1 *

(non ha bisogno di dare soluzione specifica, solo se si può fare)

La mia idea sarebbe per provare tutte le soluzioni. Ad esempio, proverei
1 * 4 * + 0 * 7 + 0 * 18 + 0 * 32 + 0 * 57 + 0 * 68 = 4
2 * 4 * + 0 * 7 + 0 * 18 + 0 * 32 + 0 * 57 + 0 * 68 = 8
3 * 4 * + 0 * 7 + 0 * 18 + 0 * 32 + 0 * 57 + 0 * 68 = 12
.....
308 641 972 * 4 * + 0 * 7 + 0 * 18 + 0 * 32 + 0 * 57 + 0 * 68 = 1234567888
308 641 973 * 4 * + 0 * 7 + 0 * 18 + 0 * 32 + 0 * 57 + 0 * 68 = 1234567892 ==> eccede
0 * 4 * + 1 * 7 + 0 * 18 + 0 * 32 + 0 * 57 + 0 * 68 = 7
1 * 4 * + 1 * 7 + 0 * 18 + 0 * 32 + 0 * 57 + 0 * 68 = 11
2 * 4 * + 1 * 7 + 0 * 18 + 0 * 32 + 0 * 57 + 0 * 68 = 15
e così via ...

Ecco il mio codice in C#:

static int toCreate = 1234567890; 
    static int[] numbers = new int[6] { 4, 7, 18, 32, 57, 68}; 
    static int[] multiplier; 
    static bool createable = false; 

    static void Main(string[] args) 
    { 
     multiplier = new int[numbers.Length]; 
     for (int i = 0; i < multiplier.Length; i++) 
      multiplier[i] = 0; 

     if (Solve()) 
     { 
      Console.WriteLine(1); 
     } 
     else 
     { 
      Console.WriteLine(0); 
     } 
    } 

    static bool Solve() 
    { 
     int lastIndex = 0; 
     while (true) 
     { 
      int comp = compare(multiplier); 
      if (comp == 0) 
      { 
       return true; 
      } 
      else if (comp < 0) 
      { 
       lastIndex = 0; 
       multiplier[multiplier.Length - 1]++; 
      } 
      else 
      { 
       lastIndex++; 
       for (int i = 0; i < lastIndex; i++) 
       { 
        multiplier[multiplier.Length - 1 - i] = 0; 
       } 
       if (lastIndex >= multiplier.Length) 
       { 
        return false; 
       } 
       multiplier[multiplier.Length - 1 - lastIndex]++; 
      } 
     } 
    } 

    static int compare(int[] multi) 
    { 
     int osszeg = 0; 
     for (int i = 0; i < multi.Length; i++) 
     { 
      osszeg += multi[i] * numbers[i]; 
     } 
     if (osszeg == toCreate) 
     { 
      return 0; 
     } 
     else if (osszeg < toCreate) 
     { 
      return -1; 
     } 
     else 
     { 
      return 1; 
     } 
    } 

Il codice funziona correttamente (per quanto ne so) ma è troppo lento. Ci vogliono circa 3 secondi per risolvere l'esempio e ci possono essere 10000 numeri da 100 numeri.

Answer 1

ho una soluzione ricorsiva. Risolve il problema originale dell'OP in circa 0,005 secondi (sulla mia macchina) e ti dice i calcoli.

private static readonly int Target = 1234567890; 
private static readonly List<int> Parts = new List<int> { 4, 7, 18, 32, 57, 68 }; 

static void Main(string[] args) 
{ 
    Console.WriteLine(Solve(Target, Parts)); 
    Console.ReadLine(); 
} 

private static bool Solve(int target, List<int> parts) 
{ 
    parts.RemoveAll(x => x > target || x <= 0); 
    if (parts.Count == 0) return false; 

    var divisor = parts.First(); 
    var quotient = target/divisor; 
    var modulus = target % divisor; 

    if (modulus == 0) 
    { 
     Console.WriteLine("{0} X {1}", quotient, divisor); 
     return true; 
    } 

    if (quotient == 0 || parts.Count == 1) return false; 

    while (!Solve(target - divisor * quotient, parts.Skip(1).ToList())) 
    { 
     if (--quotient != 0) continue; 
     return Solve(target, parts.Skip(1).ToList()); 
    } 

    Console.WriteLine("{0} X {1}", quotient, divisor); 
    return true; 
} 

Fondamentalmente, passa attraverso ciascun numero per vedere se c'è una possibile soluzione "sotto" è dato il quoziente corrente e il numero. Se non lo è, sottrae 1 dal quoziente e riprova. Lo fa finché non esaurisce tutte le opzioni per quel numero e poi passa al numero successivo, se disponibile. Se tutti i numeri sono esauriti, non c'è soluzione.

Answer 2

Non hanno i mezzi per testare la soluzione, ma il seguente dovrebbe fare.

dato un numero di destinazione target e una serie di numeri validi numbers:

bool FindDecomposition(int target, IEnumerable<int> numbers, Queue<int> decomposition) 
{ 
    foreach (var i in numbers) 
    { 
     var remainder = target % i; 

     if (remainder == 0) 
     { 
      decomposition.Enqueue(i); 
      return true; 
     } 

     if (FindDecomposition(remainder, numbers.Where(n => n < i), decomposition)) 
     { 
      return true; 
     } 
    } 

    return false 
} 

costruzione n da decomposition è abbastanza semplice.

Answer 3

Si può sempre provare a utilizzare la funzione modulo in combinazione con le espressioni LINQ per risolvere il problema.

Si dovrebbe avere una lista e una variabile modulo in esecuzione per tenere traccia di dove ci si trova nella propria iterazione. Quindi usa semplicemente la ricorsione per determinare se hai rispettato o meno le condizioni.

Un esempio potrebbe essere il seguente:

static int toCreate = 1234567890; 
    static List<int> numbers = new List<int> { 4, 7 }; 


    static void Main(string[] args) 
    { 
     numbers.Sort(); 
     numbers.Reverse(); 

     Console.WriteLine(Solve(numbers,toCreate).ToString()); 
    } 

    static bool Solve(List<int> lst1, int runningModulo) 
    { 
     if (lst1.Count == 0 && runningModulo != 0) 
      return false; 
     if (lst1.Count == 0 || runningModulo == 0) 
      return true; 

     return numbers.Any(o => o < (toCreate % lst1.First())) ? //Are there any in the remaining list that are smaller in value than the runningModulo mod the first element in the list. 
      Solve(lst1.Where(o => o != lst1.First()).ToList(), runningModulo % lst1.First()) //If yes, then remove the first element and set the running modulo = to your new modulo 
      : Solve(lst1.Where(o => o != lst1.First()).ToList(), toCreate); //Otherwise, set the running modulo back to the original toCreate value. 
    }