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

来源：学生作业帮编辑：百度作业网作业帮分类：综合作业时间：2024/06/24 18:30:34

数组中任选几个数相加,使其等于一个给定的值.请给出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

数组中任选几个数相加,使其等于一个给定的值.请给出c++实现或者算法描述. 用JAVA或者C/C++实现：在3*4的二维数组中提取每一列的一个值相加,并求出相加后的最小值! 求算法问题：一个数组a中有n个整数,如何设计算法,使其中相同的数只有一个.并给出程序. 排列组合算法如何实现一维数组中元素的排列组合,并将其排列组合的所有情况输出?如：一个字符串数组 ABC；排列后输出：在Excel中,给定几个数字,求出哪些相加能最接近或等于某个数. 若任意给定100个正实数,如何求这100个数的最大值?请帮忙给出算法或者流程图 C++ 算法问题根据输入计算一个数组中N个数相加的所有组合 c语言二维数组排序给定一个10*10的矩阵a,编一程序实现a[i1][j1] 关于数据结构单链表的题,给定两个多项式,实现多项式的相加算法, 如何实现在Excel表的一组数据中找出任意几个数相加等于指定数据的? 以有一个已排好的数组,今输入一个数,要求按原来排序的规律将它插入数组中?求其算法或c语言程序? C语言,编辑一个函数fun统计给定数组中奇数和偶数的个数