Question

数组中任选几个数相加，使其等于一个给定的值。请给出c++实现或者算法描述。

比如：1、1、1、1、2、4、2这几个数，是否可以选出若干数，使其相加等于6.。。。给出通俗易懂的算法描述最好不过了。

Answer 1

这个问题又称为“子集和问题”（也就是给定一个整数集合和一个定值，从一个集合中选取一个子集，使得子集中所有数的和等于给定的值，具体的可以百度，google 子集和问题），这是一个NP完全问题，不存在多项式时间的解，所以没有好的算法。

算法可以网上搜一下。
下面是我替你搜的的一个（回溯法：遇到合适的就取，取到后面的时候满足不了，就后退，重新取下一个满足的）：
输入：数组长度 定值
数组中的数
例如：5 10
4 5 2 6 2
输出 ： 4 6
#include <iostream>
using namespace std;
#include <stdio.h>
int len;
int sum;
int data[100000]; // 数据.
char output[100000]; // 所求子集元素，与输入数据对应，'Y'为取.‘N’为不取
void GetInput(){
int i;
cin >> len >> sum ;
for(i = 0; i < len; i++){
scanf("%d", &data[i]);
output[i] = 'N';
}
}
int GetRes(){
int p = 0; // 指向当前值.
int temp = 0; // 当前子集合和.
while(p >= 0){
if('N' == output[p]){
// 选中当前项.
output[p] = 'Y';
temp += data[p];
if(temp == sum){
return 1;
}
else if(temp > sum){
output[p] = 'N';
temp -= data[p];
}
p++;
}
if(p >= len){
while('Y' == output[p-1]){
p--;
output[p] = 'N';
temp -= data[p];
if(p < 1){
return 0;
}
}
while('N' == output[p-1]){
p--;
if(p < 1){
return 0;
}
}
output[p-1] = 'N';
temp -= data[p-1];
}
}
return 0;
}
void PrintRes(){
int i ;
for(i = 0; i < len; i++)
{
if('Y' == output[i])
{
// best[k]=data[i];
cout<<data[i]<<" ";
// k++;
}
}
cout<<endl;
// for( i = 0 ; i < k-1 ; i ++ )
//cout << best[i] << " ";
//cout<<best[i]<<endl;
}
int main()
{
GetInput();
if(GetRes())
{
PrintRes();
}
else
{
cout<<"No Solution!"<<endl;
}
return 0;
}

Answer 2

void count(int*a,n)
{
int count1[5]=;
for(int i=0;i<n;i++)
{
if(a[i]>=0&&a[i]<=20)
count1[0]++;
else
if(a[i]>=21&&a[i]<=50)
count1[1]++;
....
...
..
printf("number in 0，20]，[21，50]，[51，80]，[81，130]，[131，200] are:\n");
for(int j=0;j<5;j++)
printf("%d%c",count1[j],' ');
}

Answer 3

从n个里取1到n个组合，挨个求和试。不过这样很有可能超时。
期待好方法

Answer 4

public static void Add()
{
List<int> nums = new List<int> { 1, 5, 8, 17, 29, 33, 39, 11, 16 };
var values = Add(0, nums, 0);
int index = 1;
string str = "任意个数相加和为33的下标数据：";
foreach (var item in values)
{
str += $@"第{index}组:{string.Join(",", item.PathIndex)} |";
index++;
}
}
public static List<Values> Add(int a, List<int> nums, int index)
{
List<Values> values = new List<Values>();
for (int i = index; i < nums.Count; i++)
{
if (a == nums[i])
continue;
else if (a + nums[i] == 33)
{
values.Add(new Values(i));
continue;
}
else if (nums[i] > 33)
continue;
else
{
var temp = Add(a + nums[i], nums, i + 1);
temp.ForEach(x => x.PathIndex.Add(i));
values.AddRange(temp);
}

}
return values;
}
public class Values
{
public Values(int i)
{
PathIndex.Add(i);
}
public List<int> PathIndex = new List<int>();
}

Answer 5

public static void Add()
{
List<int> nums = new List<int> { 1, 5, 8, 17, 29, 33, 39, 11, 16 };
var values = Add(0, nums, 0);
int index = 1;
string str = "任意个数相加和为33的下标数据：";
foreach (var item in values)
{
str += $@"第{index}组:{string.Join(",", item.PathIndex)} |";
index++;
}
}
public static List<Values> Add(int a, List<int> nums, int index)
{
List<Values> values = new List<Values>();
for (int i = index; i < nums.Count; i++)
{
if (a == nums[i])
continue;
else if (a + nums[i] == 33)
{
values.Add(new Values(i));
continue;
}
else if (nums[i] > 33)
continue;
else
{
var temp = Add(a + nums[i], nums, i + 1);
temp.ForEach(x => x.PathIndex.Add(i));
values.AddRange(temp);
}

}
return values;
}
public class Values
{
public Values(int i)
{
PathIndex.Add(i);
}
public List<int> PathIndex = new List<int>();
}