Как я могу определить, можно ли составить определенное число из набора чисел?

Question

Итак, у меня есть целое число, например, 1234567890, и заданный набор чисел, например, {4, 7, 18, 32, 57, 68}.

Вопрос в том, можно ли составить 1234567890 из указанных чисел (вы можете использовать число более одного раза, и вам не нужно использовать их все). В случае выше, одно решение:
38580246 * 32 + 1 * 18

(Не нужно давать конкретное решение, только если это можно сделать)

Моя идея состоит в том, чтобы попробовать все решения. Например я бы попробовал
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 ==> превышает
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
и так далее...

Вот мой код в 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;
        }
    }

Код работает нормально (насколько я знаю), но слишком медленно. Для решения примера требуется около 3 секунд, и может быть 10000 чисел, чтобы сделать из 100 чисел.

Answer 1

У меня есть рекурсивное решение. Он решает исходную проблему ОП примерно за 0,005 секунды (на моей машине) и сообщает вам расчеты.

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;
}

В основном, он проходит через каждое число, чтобы увидеть, есть ли возможное решение "ниже", учитывая текущее частное и число. Если нет, он вычитает 1 из частного и пытается снова. Он делает это до тех пор, пока не исчерпает все опции для этого номера, а затем переходит к следующему номеру, если он доступен. Если все числа исчерпаны, решения не существует.

Answer 2

Нет средств для проверки решения, но следует сделать следующее.

Учитывая целевое число target и набор 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
}

Наращивание n от decomposition это довольно просто.

Answer 3

Вы всегда можете попробовать использовать функцию modulo в сочетании с выражениями LINQ для решения проблемы.

У вас будет список и рабочая переменная по модулю, чтобы отслеживать, где вы находитесь в своей итерации. Затем просто используйте рекурсию, чтобы определить, соответствуете ли вы условиям.

Одним из примеров будет следующий:

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.
    }