Рассчитайте все возможности получения N, используя значения из заданного набора

Ответ 1

Это проблема, которую должно решить динамическое программирование.

Создайте массив с индексами от 1 до 50. Установите каждую запись в -1. Для каждого элемента, который находится в вашем входном массиве, установите этот элемент в массив равным 0. Затем для каждого целого числа от n = 2 до 50 найдите все возможные способы суммирования с n. Количество требуемых сумм - это минимум двух слагаемых плюс 1. В конце получим элемент с индексом 50.

Ответ 2

Изменить. Из-за неверного истолкования вопроса я сначала ответил эффективным способом расчета количества возможностей (а не самих возможностей), чтобы получить N, используя значения из заданного набора. Это решение можно найти в нижней части этой публикации в качестве ссылки для других людей, но сначала я дам правильный ответ на ваши вопросы.

Создайте все возможности, посчитайте их и дайте кратчайший

При создании решения вы рассматриваете каждый элемент из входного массива и спрашиваете себя: "Должен ли я использовать это в своем решении или нет?". Поскольку мы не знаем ответа до момента вычисления, нам просто нужно попробовать как использовать его, так и не использовать его, как это видно на этапе рекурсии в приведенном ниже коде.

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

Я добавил необязательную привязку (от branch and bound") к алгоритму, который остановит расширение текущего частичного решения, если оно что это решение никогда не будет короче, чем кратчайшее решение, найденное до сих пор.

package otherproblems;

import java.util.Deque;
import java.util.LinkedList;

public class GeneratePossibilities
{
    // Input
    private static int n = 50;
    // If the input array is sorted ascending, the shortest solution is
    // likely to be found somewhere at the end.
    // If the input array is sorted descending, the shortest solution is
    // likely to be found somewhere in the beginning.
    private static int[] input = {100, 80, 66, 25, 4, 2, 1};

    // Shortest possibility
    private static Deque<Integer> shortest;
    // Number of possibilities
    private static int numberOfPossibilities;

    public static void main(String[] args)
    {
        calculate(0, n, new LinkedList<Integer>());
        System.out.println("\nAbove you can see all " + numberOfPossibilities +
            " possible solutions,\nbut this one the shortest: " + shortest);
    }

    public static void calculate(int i, int left, Deque<Integer> partialSolution)
    {
        // If there nothing left, we reached our target
        if (left == 0)
        {
            System.out.println(partialSolution);
            if (shortest == null || partialSolution.size() < shortest.size())
                shortest = new LinkedList<Integer>(partialSolution);
            numberOfPossibilities++;
            return;
        }
        // If we overshot our target, by definition we didn't reach it
        // Note that this could also be checked before making the
        // recursive call, but IMHO this gives a cleaner recursion step.
        if (left < 0)
            return;
        // If there are no values remaining, we didn't reach our target
        if (i == input.length)
            return;

        // Uncomment the next two lines if you don't want to keep generating
        // possibilities when you know it can never be a better solution then
        // the one you have now.
//      if (shortest != null && partialSolution.size() >= shortest.size())
//          return;

        // Pick value i. Note that we are allowed to pick it again,
        // so the argument to calculate(...) is i, not i+1.
        partialSolution.addLast(input[i]);
        calculate(i, left-input[i], partialSolution);
        // Don't pick value i. Note that we are not allowed to pick it after
        // all, so the argument to calculate(...) is i+1, not i.
        partialSolution.removeLast();
        calculate(i+1, left, partialSolution);
    }

}

Вычислите количество возможностей эффективно

Это хороший пример динамического программирования. Что вам нужно сделать, так это выяснить, сколько возможностей для формирования числа x, используя значение y в качестве последнего добавления и используя только значения, меньшие или равные y. Это дает вам рекурсивную формулу, которую вы можете легко перевести на решение с помощью динамического программирования. Я не совсем уверен, как записать здесь математику, но так как вы все равно их не интересовались, вот код, чтобы решить ваш вопрос:)

import java.util.Arrays;

public class Possibilities
{
    public static void main(String[] args)
    {
        // Input
        int[] input = {100, 80, 66, 25, 4, 2, 1};
        int n = 50;

        // Prepare input
        Arrays.sort(input);

        // Allocate storage space
        long[][] m = new long[n+1][input.length];

        for (int i = 1; i <= n; i++)
            for (int j = 0; j < input.length; j++)
            {
                // input[j] cannot be the last value used to compose i
                if (i < input[j])
                    m[i][j] = 0;
                // If input[j] is the last value used to compose i,
                // it must be the only value used in the composition.
                else if (i == input[j])
                    m[i][j] = 1;
                // If input[j] is the last value used to compose i,
                // we need to know the number of possibilities in which
                // i - input[j] can be composed, which is the sum of all
                // entries in column m[i-input[j]].
                // However, to avoid counting duplicates, we only take
                // combinations that are composed of values equal or smaller
                // to input[j].
                else
                    for (int k = 0; k <= j; k++)
                        m[i][j] += m[i-input[j]][k];
            }

        // Nice output of intermediate values:
        int digits = 3;
        System.out.printf(" %"+digits+"s", "");
        for (int i = 1; i <= n; i++)
            System.out.printf(" %"+digits+"d", i);
        System.out.println();
        for (int j = 0; j < input.length; j++)
        {
            System.out.printf(" %"+digits+"d", input[j]);
            for (int i = 1; i <= n; i++)
                System.out.printf(" %"+digits+"d", m[i][j]);
            System.out.println();
        }

        // Answer:
        long answer = 0;
        for (int i = 0; i < input.length; i++)
            answer += m[n][i];
        System.out.println("\nThe number of possibilities to form "+n+
            " using the numbers "+Arrays.toString(input)+" is "+answer);
    }
}

Ответ 3

Это проблема с целочисленным рюкзаком, которая является одной из наиболее распространенных NP-полных проблем; если вы находитесь в разработке/исследовании алгоритмов, проверьте их. Чтобы найти лучшее, я думаю, у вас нет выбора, кроме как вычислить их все и сохранить самый маленький.

Для правильного решения существует рекурсивный алгоритм, который довольно просто собрать.

import org.apache.commons.lang.ArrayUtils;
import java.util.*;

public class Stuff {

    private final int target;
    private final int[] steps;


    public Stuff(int N, int[] steps) {
        this.target = N;
        this.steps = Arrays.copyOf(steps, steps.length);
        Arrays.sort(this.steps);
        ArrayUtils.reverse(this.steps);
        this.memoize = new HashMap<Integer, List<Integer>>(N);
    }

    public List<Integer> solve() {
        return solveForN(target);
    }

    private List<Integer> solveForN(int N) {
        if (N == 0) {
            return new ArrayList<Integer>();
        } else if (N > 0) {
            List<Integer> temp, min = null;
            for (int i = 0; i < steps.length; i++) {
                temp = solveForN(N - steps[i]);
                if (temp != null) {
                    temp.add(steps[i]);
                    if (min == null || min.size() > temp.size()) {
                        min = temp;
                    }
                }
            }
            return min;
        } else {
            return null;
        }
    }
}

Это основано на том факте, что "добраться до N" вы пришли из N-шагов [0] или N-шагов 1,...

Таким образом, вы начинаете с вашей общей суммы N и вычитаете один из возможных шагов и делаете это снова, пока не достигнете 0 (верните список, чтобы указать, что это допустимый путь) или ниже (возвращайте null, чтобы вы не могли верните недопустимый путь).

Сложность этого правильного решения экспоненциальна! Что ДЕЙСТВИТЕЛЬНО плохо! Что-то вроде O (k ^ M), где M - размер массива steps и k константа.

Чтобы получить решение этой проблемы за меньшее время, вам придется использовать эвристику (аппроксимацию), и у вас всегда будет определенная вероятность получить неправильный ответ.

Вы можете сделать свою собственную реализацию быстрее, запомнив самую короткую комбинацию, видимую до сих пор для всех целей (так что вам не нужно повторно пересчитывать recur (N, _, шаги), если вы уже это сделали). Этот подход называется динамическим программированием. Я позволю вам сделать это самостоятельно (очень забавный материал и на самом деле не такой сложный).

Ограничения этого решения: вы найдете решение только в том случае, если вы гарантируете, что входной массив (шаги) будет отсортирован в порядке убывания и что вы пройдете его в этом порядке.

Вот ссылка на общую проблему Knapsack, если вы также хотите найти аппроксимационные решения: http://en.wikipedia.org/wiki/Knapsack_problem

Ответ 4

Вам нужно решить каждую проблему и сохранить решение. Например:

1 может быть только 1. 2 может быть 2 или 1 + 1. 4 может быть 4 или 2 + 2 или 2 + 1 + 1 или 1 + 1 + 1 + 1. Таким образом, вы берете каждое вспомогательное решение и храните его, поэтому, когда вы видите 25 = 4 + 4 + 4 + 4 + 4 + 4 + 1, вы уже знаете, что каждый 4 также может быть представлен как одна из трех комбинаций.

Затем вам нужно отсортировать цифры и проверить, чтобы избежать дублирования шаблонов, поскольку, например, (2 + 2) + (2 + 2) + (2 + 2) + (1 + 1 + 1 + 1) + ( 1 + 1 + 1 + 1) + (1 + 1 + 1 + 1) == (2 + 1 + 1) + (2 + 1 + 1) + (2 + 1 + 1) + (2 + 1 + 1 ) + (2 + 1 + 1) + (2 + 1 + 1). Шесть 2 и двенадцать 1 в обоих случаях.

Это имеет смысл?

Ответ 5

Рекурсия должна быть самым простым способом решить эту проблему (предполагая, что вы действительно хотите найти все решения проблемы). Самое приятное в этом подходе - если вы хотите просто найти кратчайшее решение, вы можете добавить проверку рекурсии и найти именно это, экономя время и пространство:)

Предполагая, что элемент i вашего массива является частью решения, вы можете решить подзадачу поиска элементов, которые суммируются с n-i. Если мы добавим упорядочение к нашему решению, например, числа в сумме должны быть от большего до наименьшего, у нас есть способ найти уникальные решения.

Это рекурсивное решение в С#, его легко перевести в java.

    public static void RecursiveSum(int n, int index, List<int> lst, List<int> solution)
    {
        for (int i = index; i < lst.Count; i++)
        {
            if (n == 0)
            {
                Console.WriteLine("");
                foreach (int j in solution)
                {
                    Console.Write(j + " ");
                }
            }
            if (n - lst[i] >= 0)
            {
                List<int> tmp = new List<int>(solution);
                tmp.Add(lst[i]);
                RecursiveSum(n - lst[i], i, lst, tmp);
            }
        }
    }

Вы вызываете его с помощью

RecursiveSum(N,0,list,new List<int>());

где N - это сумма, которую вы ищете, 0 не следует изменять, список - это список разрешенных номеров, и последний параметр также не должен изменяться.

Ответ 6

Как насчет использования жадного алгоритма n times (n - количество элементов в вашем массиве), каждый раз выбирая самый большой элемент из списка. Например. (на некотором случайном языке псевдокода):

array = [70 30 25 4 2 1]
value = 50

sort(array, descending)

solutions = []  // array of arrays

while length of array is non-zero:
    tmpValue = value
    thisSolution = []
    for each i in array:
        while tmpValue >= i:
            tmpValue -= i
            thisSolution.append(i)

    solutions.append(thisSolution)

    array.pop_first() // remove the largest entry from the array

Если вы запускаете с помощью набора [70 30 25 4 2 1] и 50, он должен дать вам массив solutions, подобный этому:

[[30 4 4 4 4 4]
 [30 4 4 4 4 4]
 [25 25]
 [4 4 4 4 4 4 4 4 4 4 4 4 2]
 [2 ... ]
 [1 ... ]]

Затем просто выберите элемент из массива решений с наименьшей длиной.

Обновить: комментарий верен, что во всех случаях это не дает правильного ответа. Причина в том, что жадный не всегда прав. Необходимо всегда использовать следующий рекурсивный алгоритм:

array = [70, 30, 25, 4, 3, 1]

def findSmallest(value, array):
    minSolution = []
    tmpArray = list(array)

    while len(tmpArray):
        elem = tmpArray.pop(0)
        tmpValue = value

        cnt = 0
        while tmpValue >= elem:
            cnt += 1
            tmpValue -= elem

            subSolution = findSmallest(tmpValue, tmpArray)

            if tmpValue == 0 or subSolution:
                if not minSolution or len(subSolution) + cnt < len(minSolution):
                    minSolution = subSolution + [elem] * cnt

    return minSolution

print findSmallest(10, array)
print findSmallest(50, array)
print findSmallest(49, array)
print findSmallest(55, array)

Печать

[3, 3, 4]
[25, 25]
[3, 4, 4, 4, 4, 30]
[30, 25]

Инвариант состоит в том, что функция возвращает либо самый маленький набор для переданного значения, либо пустой набор. Затем он может быть использован рекурсивно со всеми возможными значениями предыдущих чисел в списке. Обратите внимание, что это сложная задача O (n!), Поэтому при больших значениях она будет медленной. Также обратите внимание, что здесь есть множество возможностей оптимизации.

Ответ 7

Разве это не проблема поиска? Если это так, просто выполните поиск по ширине.

abstract class Numbers {
  abstract int total();

  public static Numbers breadthFirst(int[] numbers, int total) {
    List<Numbers> stack = new LinkedList<Numbers>();
    if (total == 0) { return new Empty(); }
    stack.add(new Empty());
    while (!stack.isEmpty()) {
      Numbers nums = stack.remove(0);
      for (int i : numbers) {
        if (i > 0 && total - nums.total() >= i) {
          Numbers more = new SomeNumbers(i, nums);
          if (more.total() == total) { return more; }
          stack.add(more);
        }
      }
    }
    return null;  // No answer.
  }
}

class Empty extends Numbers {
  int total() { return 0; }
  public String toString() { return "empty"; }
}
class SomeNumbers extends Numbers {
  final int total;
  final Numbers prev;
  SomeNumbers(int n, Numbers prev) {
    this.total = n + prev.total();
    this.prev = prev;
  }
  int total() { return total; }
  public String toString() {
    if (prev.getClass() == Empty.class) { return "" + total; }
    return prev + "," + (total - prev.total());
  }

}

Ответ 8

Задача, которую вы представляете, интересна, но очень сложна. Я бы подошел к этому, используя что-то вроде OptaPlanner (ранее Drools Planner). Трудно описать полное решение этой проблемы, не тратя много времени, но с помощью optaplanner вы также можете получить ответы типа "ближайшего соответствия" и иметь дополнительные "ходы", которые позволят более эффективно решать вашу проблему. Удачи.

Ответ 9

Это решение в python: Ideone ссылка

# Start of tsum function
def tsum(currentSum,total,input,record,n):
     if total == N :
        for i in range(0,n):
            if record[i]:
                print input[i]

            i = i+1
            for i in range(i,n):
                if record[i]:
                    print input[i]
            print ""
            return
     i=currentSum
     for i in range(i,n):
         if total+input[i]>sum :
             continue
         if i>0 and input[i]==input[i-1] and not record[i-1] :
             continue
         record[i]=1
         tsum(i+1,total+input[i],input,record,l)
         record[i]=0

# end of function
# Below portion will be main() in Java
record = []
N = 5
input = [3, 2, 2, 1, 1]
temp = list(set(input))
newlist = input
for i in range(0, len(list(set(input)))):
    val = N/temp[i]
    for j in range(0, val-input.count(temp[i])):
        newlist.append(temp[i])

# above logic was to create a newlist/input i.e [3, 2, 2, 1, 1, 1, 1, 1] 
# This new list contains the maximum number of elements <= N 
# for e.g appended three 1 as sum of new three 1 + existing two 1 <= N(5) where as
# did not append another 2 as 2+2+2 > N(5) or 3 as 3+3 > N(5)

l = len(input)

for i in range(0,l):
    record.append(0)
print "all possibilities to get N using values from a given set:"

tsum(0,0,input,record,l)

OUTPUT: для набора [3, 2, 2, 1, 1], взяв небольшой набор и маленький N для демонстрационной цели. Но хорошо работает и для более высокого значения N.

При N = 5

все возможности получить N, используя значения из заданного набора: 3 2

3 1 1

2 2 1

2 1 1 1

1 1 1 1 1

При N = 3

все возможности получить N, используя значения из заданного набора: 3

2 1

1 1 1

Ответ 10

Я сделал небольшую программу, чтобы помочь с одним решением. Лично я считаю, что лучшим было бы детерминированное математическое решение, но сейчас мне не хватает кофеина, чтобы даже подумать о том, как его реализовать. =)

Вместо этого я пошел с SAR-подходом. Stop and Reverse - метод, используемый для торговли акциями (http://daytrading.about.com/od/stou/g/SAR.htm) и в значительной степени используется для вычисления оптимальных кривых с минимальным выводом. Википедия для параболического SAR выглядит следующим образом:

'Параболический SAR вычисляется почти независимо для каждого тренда в цене. Когда цена находится в восходящем тренде, SAR появляется ниже цена и сходится вверх к ней. Аналогичным образом, на нисходящий тренд, SAR выходит выше цены и сходится вниз.

Я адаптировал его к вашей проблеме. Я начинаю со случайного значения из вашей серии. Затем код вводит конечное число итераций.

Я выбираю другое случайное значение из серии. Если новое значение плюс сумма стека уступает цели, значение добавлено; если выше, то уменьшилось. Я могу продолжать столько, сколько захочу, пока не удовлетворю условию (стек sum = target), или прервется, если цикл не сможет найти правильное решение. В случае успеха я записываю стек и количество итераций. Затем я переделываю все.

Далее следует ЭКСТРЕМАЛЬНЫЙ грубый код. Пожалуйста, простите торопливость. О, и это в С#. =)

Опять же, это не гарантирует, что вы получите оптимальный путь; это подход грубой силы. Он может быть усовершенствован; если есть идеальное совпадение для целевого попадания, например.

 public static class SAR
 {
    //I'm considering Optimal as the smallest signature (number of members).
    // Once set, all future signatures must be same or smaller.

    private static Random _seed = new Random();

    private static List<int> _domain = new List<int>() { 100, 80, 66, 24, 4, 2, 1 };

    public static void SetDomain(string domain)
    {
        _domain = domain.Split(',').ToList<string>().ConvertAll<int>(a => Convert.ToInt32(a));
        _domain.Sort();
    }

    public static void FindOptimalSAR(int value)
    {
        // I'll skip some obvious tests. For example:
        //   If there is no odd number in domain, then
        //   it impossible to find a path to an odd
        //   value.

        //Determining a max path run. If the count goes
        //   over this, it useless to continue.
        int _maxCycle = 10;

        //Determining a maximum number of runs.
        int _maxRun = 1000000;
        int _run = 0;

        int _domainCount = _domain.Count;

        List<int> _currentOptimalSig = new List<int>();
        List<String> _currentOptimalOps = new List<string>();
        do
        {

            List<int> currSig = new List<int>();
            List<string> currOps = new List<string>();

            int _cycle = 0;
            int _cycleTot = 0;
            bool _OptimalFound = false;

            do
            {
                int _cursor = _seed.Next(_domainCount);

                currSig.Add(_cursor);

                if (_cycleTot < value)
                {
                    currOps.Add("+");
                    _cycleTot += _domain[_cursor];
                }
                else
                {
                    // Your situation doesn't allow for negative
                    // numbers. Otherwise, just enable the two following lines.
                    // currOps.Add("-");
                    // _cycleTot -= _domain[_cursor];
                }

                if (_cycleTot == value)
                {
                    _OptimalFound = true;
                    break;
                }

                _cycle++;
            } while (_cycle < _maxCycle);

            if (_OptimalFound)
            {
                _maxCycle = _cycle;

                _currentOptimalOps = currOps;
                _currentOptimalSig = currSig;

                Console.Write("Optimal found: ");

                for (int i = 0; i < currSig.Count; i++)
                {
                    Console.Write(currOps[i]);
                    Console.Write(_domain[currSig[i]]);
                }

                Console.WriteLine(".");
            }

            _run++;

        } while (_run < _maxRun);
    }
}

И это вызывающий:

        String _Domain = "100, 80, 66, 25, 4, 2, 1";

        SAR.SetDomain(_Domain);

        Console.WriteLine("SAR for Domain {" + _Domain + "}");
        do
        {
            Console.Write("Input target value: ");
            int _parm = (Convert.ToInt32(Console.ReadLine()));

            SAR.FindOptimalSAR(_parm);
            Console.WriteLine("Done.");

        } while (true);

Это мой результат после истребителей 100k для нескольких целей, учитывая слегка измененную серию (я переключил 25 на 24 для целей тестирования):

SAR for Domain {100, 80, 66, 24, 4, 2, 1}
Input target value: 50
Optimal found: +24+24+2.
Done.
Input target value: 29
Optimal found: +4+1+24.
Done.
Input target value: 75
Optimal found: +2+2+1+66+4.
Optimal found: +4+66+4+1.
Done.

Теперь с вашей оригинальной серией:

SAR for Domain {100, 80, 66, 25, 4, 2, 1}
Input target value: 50
Optimal found: +25+25.
Done.
Input target value: 75
Optimal found: +25+25+25.
Done.
Input target value: 512
Optimal found: +80+80+66+100+1+80+25+80.
Optimal found: +66+100+80+100+100+66.
Done.
Input target value: 1024
Optimal found: +100+1+80+80+100+2+100+2+2+2+25+2+100+66+25+66+100+80+25+66.
Optimal found: +4+25+100+80+100+1+80+1+100+4+2+1+100+1+100+100+100+25+100.
Optimal found: +80+80+25+1+100+66+80+80+80+100+25+66+66+4+100+4+1+66.
Optimal found: +1+100+100+100+2+66+25+100+66+100+80+4+100+80+100.
Optimal found: +66+100+100+100+100+100+100+100+66+66+25+1+100.
Optimal found: +100+66+80+66+100+66+80+66+100+100+100+100.
Done.

Минусы: Следует еще раз упомянуть: этот алгоритм не гарантирует, что вы найдете оптимальные значения. Он делает приближение грубой силы.

Профи: быстрый. Итерации 100 тыс. Изначально могут показаться много, но алгоритм начинает игнорировать длинные пути после обнаружения всех и более оптимизированных путей, поскольку он уменьшает максимально допустимое количество циклов.