作业帮数组中任选几个数相加,使其等于一个给定的值.请给出c++实现或者算法描述.比如：1、1、1、1、2、4、2这几个数,是否可以选出若干数,使其相加等于6..给出通俗易懂的算法描述最好不过了.
来源：学生作业帮助网 编辑：作业帮 时间：2024/04/29 03:09:04
数组中任选几个数相加,使其等于一个给定的值.请给出c++实现或者算法描述.比如：1、1、1、1、2、4、2这几个数,是否可以选出若干数,使其相加等于6..给出通俗易懂的算法描述最好不过了.
数组中任选几个数相加,使其等于一个给定的值.请给出c++实现或者算法描述.
比如：1、1、1、1、2、4、2这几个数,是否可以选出若干数,使其相加等于6..给出通俗易懂的算法描述最好不过了.
数组中任选几个数相加,使其等于一个给定的值.请给出c++实现或者算法描述.比如：1、1、1、1、2、4、2这几个数,是否可以选出若干数,使其相加等于6..给出通俗易懂的算法描述最好不过了.
这个问题又称为“子集和问题”（也就是给定一个整数集合和一个定值,从一个集合中选取一个子集,使得子集中所有数的和等于给定的值,具体的可以百度,google 子集和问题）,这是一个NP完全问题,不存在多项式时间的解,所以没有好的算法.
算法可以网上搜一下.
下面是我替你搜的的一个（回溯法：遇到合适的就取,取到后面的时候满足不了,就后退,重新取下一个满足的）：
输入：数组长度 定值
数组中的数
例如：5 10
4 5 2 6 2
输出 ：4 6
#include
using namespace std;
#include
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