我的目标是找到所有可能的组合,总和达到给定的总数。
例如,如果数组是
2 59 3 43 5 9 8 62 10 4 如果总数为 12,则可能的组合为
2 10
3 9
8 4
5 3 4
这是我编写的第一组代码。想知道对此可以进行的最佳改进。
int find_numbers_matching_sum(int *number_coll, int total)
{
int *search_till = lower_bound(number_coll,number_coll+TOTAL_SIZE, total);
int location = search_till - number_coll;
if (*search_till > total && location > 0 )
{
--location;
}
while ( location >= 0 )
{
find_totals(number_coll,total,location);
--location;
}
return 1;
}
int find_totals(int *number_coll, int total, int end_location)
{
int left_ones = total - number_coll[end_location];
int curloc = end_location;
int *search_till = 0;
int location ;
int all_numbers[10];
int i = 0;
all_numbers[i] = number_coll[end_location];
while ( left_ones && curloc >= 0 )
{
search_till = lower_bound(number_coll,number_coll+end_location, left_ones);
location = search_till - number_coll;
if (*search_till > left_ones && location > 0 )
{
--location;
}
else if ( left_ones < *search_till )
{
break;
}
curloc=location;
left_ones = left_ones - number_coll[curloc];
all_numbers[++i] = number_coll[curloc];
end_location = curloc - 1;
}
if ( !left_ones )
{
while ( i>=0)
{
cout << all_numbers[i--] << ' ';
}
}
cout << endl;
return 1;
}
您描述的问题也称为子集和问题 http://en.wikipedia.org/wiki/Subset_sum_problem这是NP完全 http://en.wikipedia.org/wiki/NP-Complete。您可以实现的最好结果是指数时间算法,该算法会尝试数组/集合的所有可能子集。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)