从数组中选取等于某个数字的数组 [英] Pick from array which is equal to some number
问题描述
我有一系列类似这样的金额：
I have an array of amounts something like this:
[ 100, 20, 80, 50, 150, 20, 10 .. ]
我必须从此数组中选择一个等于某个数量（例如200）的数组。
I have to pick from this array which is equal to some amount, say 200.
因此，数量将从数组中选取150、50。
So, the amounts will be 150, 50 picked from the array.
我可以构建一个算法可以一次又一次地遍历数组并检查数量是否相等，但是我想知道是否有一种简单的方法吗？
I can build an algorithm which can iterate through the array again and again and check if amount is equal or not, but I want to know if is there an easy way?
还是我必须写一个
谢谢。
示例解释： >
我有一个数组。 说-> 100、200、300
我还有另一个数组。 说-> 50,50,20,10,20,150,150,50,70,30
I have a another array. Say -> 50,50,20,10,20,150,150,50,70,30
我想通过从第一个数组（即100），如果第二个数组匹配，则按第二个数组中的数字之和进行匹配，否则，我将跳过它并尝试使用数组中的下一个数字（即200）。
I want to match by picking up a number from the first array(i.e 100) and matching by sum of numbers from the second array if it matches, else fine, I will skip it and try it for the next number (i.e. 200) in the array.
编辑：一些澄清
该数组不包含完全匹配项。我之前将其匹配并从数组中删除。因此，它仅包含可以完全相同的数字。
The array does not contain the exact matches. I matched it previously and removed from the array. So it only contains numbers that can be exactly the same.
如果任何金额与给定金额都不匹配，这很好。如果数组中的总和不匹配，我将跳过。
It is fine if any sum is not matched by the given amount. I will simply skip if sum from array doesn't match.
推荐答案
The problem you try to solve is called subset sum problem and belongs to NP-complete problems.
给出一组整数和一个整数s，将任何非空子集
求和到s（ ...）
Given a set of integers and an integer s, does any non-empty subset sum to s (...)
没有多项式时间算法可以解决已知的问题（此刻；））。
如果您的集合中包含 O（2 ^ n），则可以检查集合的所有子集 n 个元素。
最终，如果您的集合将是一个无限集合，则可以尝试解决变更问题。
No polynomial-time algorithm to solve this problem is known (at the moment ;)).
You can check all subsets of your set which is O(2^n) if your set contains n elements.
Eventually if your set would be an infinite set, you could try solving the change-making problem.
仍然可以解决（如我上面所写的指数复杂性）。考虑一个函数：
Still it can be solved (exponential complexity as I wrote above). Consider a function:
bool foundSum(set[], n, sum);
如果可以找到总和，则返回 true ， false 否则。一个简单的递归算法：
which returns true if the sum can be found, false otherwise. A simple recursive algorithm:
foundSum（set，n，sum）= foundSum（set，n-1，sum）或foundSum（arr， n-1，sum-set [n-1]）
它是如何工作的？在每个步骤中，您检查是否将最后一个元素包括在内/排除在外。
How it works? In each step you check if the sum can be obtained if you in/exclude last element.
C ++中的示例实现（可以很容易地用Java编写）：
Example implementation in C++ (can be easily written in Java):
bool foundSum(vector<int> set, int n, int sum) {
if(sum == 0) return true;
if(n == 0 and sum != 0) return false;
int last = set[n-1];
if(last > sum) return foundSum(set, n-1, sum);
return foundSum(set,n-1,sum) or foundSum(set,n-1,sum-last);
}
修改为在找到答案时打印子集： http://ideone.com/YysY2n
Modified to print subset when answer is found: http://ideone.com/YysY2n
这篇关于从数组中选取等于某个数字的数组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
