子集和问题（算法分析与设计）
(2013-05-02 21:36:26)
问题描述：子集和问题的一个实例为（S，t）.其中，S={x1,x2,....xn}是一个正整数的集合，c是一个正整数。子集和问题判定是否存在S的一个自己S1，使得
累加和为c.
算法设计：对于给定的正整数的集合S={x1,x2,....xn}和正整数c，计算S的一个自己S1，使得累加和为c。
数据输入：第一行有2个正整数n和c，n表示S的大小，c是自己和的目标值。接下来的1行中，有n个正整数，表示集合S中的元素。
结果输出：将子集和问题的解输出。当无解时，输出“No Solution!”
例如：
输入：
5
10
2 2 6
5 4
输出：
2 2
6
代码：
#include
#include
int a[100];
int b[100];
int n , c;
int best = 0;
int max = 0;
int mutex = 0;
bool flag = false;
void Backtrack(int i){
if(i >= n){
mutex = 1;
if(max > best)
best =
max;
return;
}
if(max+a[i] ==
c){
b[i] = a[i];
printf("%d\n", max + a[i]);
for(i=0; i
if(b[i] !=
0){
printf("%d ", b[i]);
}
}
printf("\n");
mutex = 1;
flag = true;
}else if(max + a[i] <
c){
mutex = 1;
max += a[i];
b[i] = a[i];
Backtrack(i + 1);
if(flag) return ;
max -= a[i];
b[i] = 0;
Backtrack(i + 1);
if(flag) return ;
}
if(!mutex) printf("No
Solution！\n");
}
int main(){
int i, sum = 0;
scanf("%d %d", &n,
&c);
for(i=0; i
scanf("%d", &a[i]);
b[i] = 0;
sum += a[i];
}
if(sum < c)
printf("No Solution！\n");
else if(sum == c){
for(i=0; i
printf("\n");
}else
Backtrack(0);
system("pause");
return 0;
}
喜欢
0
赠金笔
加载中，请稍候......
加载中…
喜欢