arrays - 使用给定集合中的值计算获得 N 的所有可能性

Question

所以这里是问题：

给定input = [100 80 66 25 4 2 1]，我需要找到给我 50 的最佳组合。

看看这个，最好是 25+25 = 50，所以我需要数组中的 2 个元素。

其他组合包括25+4+4+4+4+4+4+1and 25+4+4+4+4+4+2+2+1.. etc etc

我需要找到所有的可能性，让我得到我想要的值的总和。

编辑：以及最好的可能性（一个术语最少的）

这是我到目前为止所做的：首先构建一个新数组（简单的循环遍历所有元素并存储在一个新的临时数组中），检查所有高于我的数组的元素（所以对于输入 50，元素 100， 80,66 更高，所以丢弃它们，然后我的新数组是 [25 4 2 1]）。然后，从这里，我需要检查组合。

我做的第一件事是一个简单的 if 语句，检查是否有任何数组元素与我想要的数字完全匹配。所以如果我想要 50，我检查 50 是否在数组中，如果没有，我需要找到组合。

我的问题是，我不完全确定如何找到每一个组合。一段时间以来，我一直在努力想出一个算法，但我总是最终被难住了。

任何帮助/提示将不胜感激。

PS - 我们可以假设数组总是按从 LARGEST 到 SMALLEST 值的顺序排序。

Answer 1

This is the kind of problem that dynamic programming is meant to solve.

Create an array with with indices, 1 to 50. Set each entry to -1. For each element that is in your input array, set that element in the array to 0. Then, for each integer n = 2 to 50, find all possible ways to sum to n. The number of sums required is the minimum of the two addends plus 1. At the end, get the element at index 50.

Answer 2

编辑：由于对问题的误解，我首先回答了一种有效的方法来计算可能性的数量（而不是可能性本身），以使用给定集合中的值获得 N 。该解决方案可以在这篇文章的底部找到，作为其他人的参考，但首先我会正确回答你的问题。

---

产生所有可能性，计算它们并给出最短的一个

生成解决方案时，您会考虑输入数组中的每个元素并问自己“我应该在我的解决方案中使用它吗？”。由于我们直到计算之后才知道答案，我们只需要尝试使用它和不使用它，如下面代码中的递归步骤所示。

现在，为了避免重复和遗漏，我们需要注意递归调用的参数。如果我们使用当前元素，我们也应该允许它在下一步中使用，因为该元素可能会被使用尽可能多的次数。因此，这个递归调用的第一个参数是i. 但是，如果我们决定不使用该元素，我们不应该允许它在下一步中使用，因为那将是当前步骤的副本。因此，这个递归调用的第一个参数是i+1.

我在算法中添加了一个可选的界限（来自“分支和界限”），如果知道这个解决方案永远不会比目前找到的最短解决方案更短，它将停止扩展当前的部分解决方案。

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's the shortest: " + shortest);
    }

    public static void calculate(int i, int left, Deque<Integer> partialSolution)
    {
        // If there's 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);
    }
}

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 - steps[0] 或 N - steps 1，...

因此，您从目标总 N 开始并减去一个可能的步骤，然后再做一次，直到您处于 0（返回一个列表以指定这是一个有效路径）或以下（返回 null 以便您不能返回一个无效的小路）。

这个正确解决方案的复杂性是指数级的！这真的很糟糕！类似于 O(k^M) 的东西，其中 M 是steps数组的大小和 ka 常数。

要在更短的时间内解决这个问题，您将不得不使用启发式（近似），并且您总是有一定的概率得到错误​​的答案。

您可以通过记住迄今为止所有目标的最短组合来加快自己的实现速度（因此，如果您已经这样做了，则无需重新计算 recur(N, _, steps)）。这种方法称为动态规划。我会让你自己做（非常有趣的东西，真的没那么复杂）。

此解决方案的约束：只有当您保证输入数组（步骤）按降序排序并且您按该顺序遍历它时，您才会找到解决方案。

如果您还想查看近似解决方案，这里是一般背包问题的链接：http ://en.wikipedia.org/wiki/Knapsack_problem

Answer 4

这不只是一个搜索问题吗？如果是这样，只需搜索广度优先。

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

}

Answer 5

递归应该是解决这个问题的最简单方法（假设你真的想找到问题的所有解决方案）。这种方法的好处是，如果您只想找到最短的解决方案，您可以添加对递归的检查并找到它，从而节省时间和空间:)

假设i您的数组元素是解决方案的一部分，您可以解决找到总和为 的元素的子问题n-i。如果我们为我们的解决方案添加一个排序，例如总和中的数字必须从大到小，我们就有办法找到唯一的解决方案。

这是 C# 中的递归解决方案，应该很容易在 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 不应更改，list 是您允许的数字列表，最后一个参数也不应更改。

Answer 6

如何使用贪心算法n时间（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

如果使用 set[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!) 的复杂性，因此对于较大的值会很慢。另请注意，这里有许多优化潜力。

Answer 7

这是python中的一个解决方案：Ideone link

# 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's as sum of new three 1's + existing two 1's <= 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)

输出：对于集合 [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

Answer 8

你提出的问题很有趣，但也很复杂。我会通过使用像OptaPlanner（以前的 Drools Planner）这样的东西来解决这个问题。如果不花费大量时间，很难描述这个问题的完整解决方案，但使用 optaplanner，您还可以获得“最接近”类型的答案，并且可以进行增量“移动”，从而更有效地解决您的问题。祝你好运。

Answer 9

您需要解决每个子问题并存储解决方案。例如：

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也可以表示为3个组合之一。

然后你必须对数字进行排序并检查以避免重复的模式，例如，(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。

那有意义吗？

Answer 10

我做了一个小程序来帮助解决一个问题。就个人而言，我认为最好的方法是确定性的数学解决方案，但现在我缺乏咖啡因，甚至无法思考如何实现它。=)

相反，我采用了 SAR 方法。Stop and Reverse 是一种用于股票交易的技术 ( http://daytrading.about.com/od/stou/g/SAR.htm )，它被大量用于以最少的推理计算最优曲线。抛物线 SAR的Wikipedia 条目如下所示：

'抛物线 SAR 几乎是针对价格的每个趋势独立计算的。当价格处于上升趋势时，SAR 出现在价格下方并向上收敛。同样，在下降趋势中，SAR 出现在价格之上并向下收敛。

我根据您的问题对其进行了调整。我从你的系列中的一个随机值开始。然后代码进入有限次数的迭代。

我从系列堆栈中选择另一个随机值。如果新值加上堆栈总和低于目标值，则添加该值；如果优越，则减少。在满足条件（堆栈总和 = 目标）之前，我可以随心所欲地继续，或者如果循环找不到有效的解决方案，则中止。如果成功，我会记录堆栈和迭代次数。然后我重做一切。

一个非常粗略的代码如下。请原谅仓促。哦，它在 C# 中。=)

同样，它不能保证您将获得最佳路径；这是一种蛮力方法。可以细化；例如，检测目标命中是否完美匹配。

 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's impossible to find a path to an odd
        //   value.

        //Determining a max path run. If the count goes
        //   over this, it's 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.

缺点：值得再次提及：此算法不保证您会找到最佳值。它进行了蛮力近似。

优点：快。100k 次迭代最初可能看起来很多，但该算法在检测到越来越多的优化路径后开始忽略长路径，因为它减少了最大允许的循环数。