数据结构实习报告
班级：13软件二班
姓名：殷健 学号：1345536225
子集和数问题
1：问题描述
子集和数问题1：子集和问题的为〈W,c〉。其中，W={w1,w2,...,wn}是一个正整数的集合，子集和数问题判定是否存在W的一个子集W1，使得∑W1=c∑W(0
2：问题分析
程序中设计了函数void computeSumofSub(int s,int k,int r)，其意义是从第k项开始，如果s（已经决策的和数）和w[k]（当前元素）之和为和数，就把结果输出来，否则如果s与，w[k],w[k+1]之和小于和数，则调用computeSumofsub(s+w[k],k+1,r-w[k])，意为选择此结点的左分支，再判断s和后面所有元素之和是否不小于M（所有的加起来都小，必定无解），并且s+w[k+1]M，也是无解），若条件符合即调用computeSumofSub(s,k+1,r-w[k])，即选择当前结点的右分支。
算法展示：
#include using namespace std; #include #include #define M 50 cla SumOfSub{ private: int w[M];
int m; int x[M]; public: SumOfSub(int a[], int b, int n){
for(int i=0;i=m&&s+w[k+1]
}; void main(){ int sum=0; int w[M]; srand((unsigned)time(NULL));
for(int i=0;i
} cout
cout
} cout>m; sum=m*sum; cout
复杂性分析: 对于不同的输入结果，算法的执行次数有所不同，最好情况是n，最坏情况是n*2^n。尽管差异很大，但当n很大时，对某些输入而言，回溯法仍可在短时间内求解。 其它说明: 按书中所讲的约束条件，程序中所有变量都是整型，输入的各元素要从小到大输入，而且不能有重复的元素。若是想要无序输入，可以程序中加入程序1.c的归并排序算法，对输入的数组排序即可。
拓展一
问题描述: 子集和数问题拓展一：子集和问题的为〈W,c，p〉。其中，W={w1,w2,...,wn}是一个正整数的集合，子集和数问题判定是否存在W的一个子集W1，使得∑W1=c∑W(0
问题分析：
增加一个数组p,使得p的每个元素与w对应元素关系为pi=Wi+10;最后结果W子集中元素个数越多，则p和最大，但也可以将每个符合条件子集对应P集合的元素和计算出做个比较，然后输出最大的再对应原W子集。
算法演示
#include using namespace std; #include #include #define M 50 cla SumOfSub{ private: int w[M];int p[M];int m; int x[M];
int N[M];int max;int j; public: SumOfSub(int a[], int b, int n){
max=0;j=0;
for(int i=0;i
w[i]=a[i];
p[i]=a[i]+10;
}
m = b;
x[0]=n; } void computeSumOfSub(int s, int k, int r){ x[k] = 1; if(s+w[k] == m){ printResult(k); cout
} else if(s+w[k]+w[k+1] =m&&s+w[k+1]
int S=0;int i;
cout
for(i=0; i
S=S+p[i];
cout
}
cout
cout
if(S>max){
max=S;
int J=0;
for(i=0;i
if(x[i]==1){
N[J]=w[i];
J++;
}
}
j=J;
} } void special(){
cout
for(int i=0;i
cout
}
cout
for(int i=0;i
w[i]=rand();
if(w[i]==0){
w[i]=rand();
}
sum=sum+w[i]; } cout
cout>m; sum=m*sum; cout
r += w[i]; } sumOfSub.computeSumOfSub(0, 0, r);
sumOfSub.special(); } 运行结果
复杂性分析
对于不同的输入结果，算法的执行次数有所不同，最好情况是n，最坏情况是n*2^n。尽管差异很大，但当n很大时，对某些输入而言，回溯法仍可在短时间内求解。
拓展二
问题描述
子集和数问题拓展一：子集和问题的为〈W,c，P〉。其中，W={w1,w2,...,wn}是一个正整数的集合，子集和数问题判定是否存在W的一个子集W1，使得∑W1=c∑W(0
问题分析
增加一个数组随机数组P，每个符合条件子集对应P集合的元素和计算出做个比较，然后输出最大的再对应原W子集。
算法演示
#include using namespace std; #include #include #define M 50 cla SumOfSub{ private: int w[M];int p[M];int m;
int x[M];int N[M];int max;int j; public: SumOfSub(int a[], int b, int n){
max=0;
j=0;
cout
for(int i=0;i
w[i]=a[i];
p[i]=rand();
cout
}
cout
m = b;
x[0]=n; } void computeSumOfSub(int s, int k, int r){ x[k] = 1; if(s+w[k] == m){ printResult(k); cout
} else if(s+w[k]+w[k+1] =m&&s+w[k+1]
int S=0;int i;
cout
for(i=0; i
S=S+p[i];
cout
}
cout
cout
if(S>max){
max=S;
int J=0;
for(i=0;i
if(x[i]==1){
N[J]=w[i];
J++;
}
}
j=J;
} } void special(){
cout
for(int i=0;i
cout
}
cout
for(int i=0;i
w[i]=rand();
if(w[i]==0){
w[i]=rand();
}
sum=sum+w[i]; } cout
cout>m; sum=m*sum; cout
r += w[i]; } sumOfSub.computeSumOfSub(0, 0, r);
sumOfSub.special(); }
运行结果
复杂性分析
对于不同的输入结果，算法的执行次数有所不同，最好情况是n，最坏情况是n*2^n。尽管差异很大，但当n很大时，对某些输入而言，回溯法仍可在短时间内求解。
