⼦集和问题（C语⾔）--回溯法
⼦集和问题
题⽬描述
给定⼀个正整数集合X={x1,x2,…,xn}和⼀个正整数c，设计回溯算法，求集合X的⼀个⼦集Y，使得Y中元素之和等于c。
解题思路
类似于全排列的思想，尝试所有结果，如果不符合则回溯
具体代码实现
#include <stdio.h>
#include <stdlib.h>
int flag=0,sum=0;
int *s, *x, n,c;
//向⽂件写⼊⼀个数字
void fileWrite(int i){
FILE *fp;
fp = fopen("i:\\算法\\回溯法\\", "a");
if (fp == NULL) {  //若打开⽂件失败则退出
printf("不能打开⽂件！\n");
return ;
}
if(i == 32767){      //如果⼀种解法读⼊完毕，则换⾏
fprintf(fp,"\n");
}
else if(i<0){      //如果输⼊⼩于0则代表第⼏种解法
fprintf(fp,"第%d种解法：",-i);
}else{
fprintf(fp,"%d ",i);
}
fclose(fp);
}
//从⽂件读取数据
void fileRead(){
FILE *fp;
fp = fopen("i:\\算法\\回溯法\\", "r");
if (fp == NULL) {  //若打开⽂件失败则退出
printf("不能打开⽂件！\n");
return ;
}
//从⽂件中读⼊S的⼤⼩n和⼦集和的⽬标值c
fscanf(fp,"%d",&n);
fscanf(fp,"%d",&c);
c语言和c++区别s=(int *)malloc(sizeof(int)*n);
x=(int *)malloc(sizeof(int)*n);
//从⽂件中读取集合S中的n正整数元素
for(int i=0;i<n;i++){
fscanf(fp,"%d",&s[i]);
x[i]=0;
}
fclose(fp);
}
void backtrack(int t){
int i;
if(t==n)
{
if(sum==c)
{
flag+=1;
fileWrite(-flag);
for(i=0;i<n;i++){
if(x[i]){
fileWrite(s[i]);
}
}
fileWrite(32767);
return;
}
}
else
{
sum+=s[t];
x[t]=1;
backtrack(t+1);
x[t]=0;
sum-=s[t];
backtrack(t+1);
}
}
int main(){
fileRead();
backtrack(0);
if(flag > 0){
printf("已将结果存⼊⽂件\n"); }
else{
printf("No Solution!\n"); }
return 0;
}

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。