你如何从给定的N个数字中测试所有可能的加法组合,使它们加起来得到给定的最终数字?
一个简单的例子:
要添加的数字集:N ={1,5,22,15,0,…} 期望结果:12345
你如何从给定的N个数字中测试所有可能的加法组合,使它们加起来得到给定的最终数字?
一个简单的例子:
要添加的数字集:N ={1,5,22,15,0,…} 期望结果:12345
当前回答
这是R中的一个解
subset_sum = function(numbers,target,partial=0){
if(any(is.na(partial))) return()
s = sum(partial)
if(s == target) print(sprintf("sum(%s)=%s",paste(partial[-1],collapse="+"),target))
if(s > target) return()
for( i in seq_along(numbers)){
n = numbers[i]
remaining = numbers[(i+1):length(numbers)]
subset_sum(remaining,target,c(partial,n))
}
}
其他回答
下面是一个更好的版本,具有更好的输出格式和c++ 11特性:
void subset_sum_rec(std::vector<int> & nums, const int & target, std::vector<int> & partialNums)
{
int currentSum = std::accumulate(partialNums.begin(), partialNums.end(), 0);
if (currentSum > target)
return;
if (currentSum == target)
{
std::cout << "sum([";
for (auto it = partialNums.begin(); it != std::prev(partialNums.end()); ++it)
cout << *it << ",";
cout << *std::prev(partialNums.end());
std::cout << "])=" << target << std::endl;
}
for (auto it = nums.begin(); it != nums.end(); ++it)
{
std::vector<int> remaining;
for (auto it2 = std::next(it); it2 != nums.end(); ++it2)
remaining.push_back(*it2);
std::vector<int> partial = partialNums;
partial.push_back(*it);
subset_sum_rec(remaining, target, partial);
}
}
下面是一个Java版本,它非常适合小N和非常大的目标和,当复杂度O(t*N)(动态解)大于指数算法时。我的版本在中间攻击中使用了一个meet,并进行了一些调整,以降低复杂度,从经典的naive O(n*2^n)降低到O(2^(n/2))。
如果你想在32到64个元素之间的集合中使用这种方法,你应该将表示step函数中当前子集的int改为long,尽管随着集合大小的增加,性能显然会急剧下降。如果你想对一个有奇数个元素的集合使用这个,你应该给这个集合加上一个0,使它成为偶数。
import java.util.ArrayList;
import java.util.List;
public class SubsetSumMiddleAttack {
static final int target = 100000000;
static final int[] set = new int[]{ ... };
static List<Subset> evens = new ArrayList<>();
static List<Subset> odds = new ArrayList<>();
static int[][] split(int[] superSet) {
int[][] ret = new int[2][superSet.length / 2];
for (int i = 0; i < superSet.length; i++) ret[i % 2][i / 2] = superSet[i];
return ret;
}
static void step(int[] superSet, List<Subset> accumulator, int subset, int sum, int counter) {
accumulator.add(new Subset(subset, sum));
if (counter != superSet.length) {
step(superSet, accumulator, subset + (1 << counter), sum + superSet[counter], counter + 1);
step(superSet, accumulator, subset, sum, counter + 1);
}
}
static void printSubset(Subset e, Subset o) {
String ret = "";
for (int i = 0; i < 32; i++) {
if (i % 2 == 0) {
if ((1 & (e.subset >> (i / 2))) == 1) ret += " + " + set[i];
}
else {
if ((1 & (o.subset >> (i / 2))) == 1) ret += " + " + set[i];
}
}
if (ret.startsWith(" ")) ret = ret.substring(3) + " = " + (e.sum + o.sum);
System.out.println(ret);
}
public static void main(String[] args) {
int[][] superSets = split(set);
step(superSets[0], evens, 0,0,0);
step(superSets[1], odds, 0,0,0);
for (Subset e : evens) {
for (Subset o : odds) {
if (e.sum + o.sum == target) printSubset(e, o);
}
}
}
}
class Subset {
int subset;
int sum;
Subset(int subset, int sum) {
this.subset = subset;
this.sum = sum;
}
}
这也可以用来打印所有的答案
public void recur(int[] a, int n, int sum, int[] ans, int ind) {
if (n < 0 && sum != 0)
return;
if (n < 0 && sum == 0) {
print(ans, ind);
return;
}
if (sum >= a[n]) {
ans[ind] = a[n];
recur(a, n - 1, sum - a[n], ans, ind + 1);
}
recur(a, n - 1, sum, ans, ind);
}
public void print(int[] a, int n) {
for (int i = 0; i < n; i++)
System.out.print(a[i] + " ");
System.out.println();
}
时间复杂度是指数级的。2^n的阶
我将c#示例移植到Objective-c,并没有在响应中看到它:
//Usage
NSMutableArray* numberList = [[NSMutableArray alloc] init];
NSMutableArray* partial = [[NSMutableArray alloc] init];
int target = 16;
for( int i = 1; i<target; i++ )
{ [numberList addObject:@(i)]; }
[self findSums:numberList target:target part:partial];
//*******************************************************************
// Finds combinations of numbers that add up to target recursively
//*******************************************************************
-(void)findSums:(NSMutableArray*)numbers target:(int)target part:(NSMutableArray*)partial
{
int s = 0;
for (NSNumber* x in partial)
{ s += [x intValue]; }
if (s == target)
{ NSLog(@"Sum[%@]", partial); }
if (s >= target)
{ return; }
for (int i = 0;i < [numbers count];i++ )
{
int n = [numbers[i] intValue];
NSMutableArray* remaining = [[NSMutableArray alloc] init];
for (int j = i + 1; j < [numbers count];j++)
{ [remaining addObject:@([numbers[j] intValue])]; }
NSMutableArray* partRec = [[NSMutableArray alloc] initWithArray:partial];
[partRec addObject:@(n)];
[self findSums:remaining target:target part:partRec];
}
}
Thank you.. ephemient
我已经将上述逻辑从python转换为php..
<?php
$data = array(array(2,3,5,10,15),array(4,6,23,15,12),array(23,34,12,1,5));
$maxsum = 25;
print_r(bestsum($data,$maxsum)); //function call
function bestsum($data,$maxsum)
{
$res = array_fill(0, $maxsum + 1, '0');
$res[0] = array(); //base case
foreach($data as $group)
{
$new_res = $res; //copy res
foreach($group as $ele)
{
for($i=0;$i<($maxsum-$ele+1);$i++)
{
if($res[$i] != 0)
{
$ele_index = $i+$ele;
$new_res[$ele_index] = $res[$i];
$new_res[$ele_index][] = $ele;
}
}
}
$res = $new_res;
}
for($i=$maxsum;$i>0;$i--)
{
if($res[$i]!=0)
{
return $res[$i];
break;
}
}
return array();
}
?>