集和的算法

‘壹’ 近似算法的子集和问题的近似算法

问题描述：设子集和问题的一个实例为〈S,t〉。其中，S={x1，x2，…，xn}是一个正整数的集合，t是一个正整数。子集和问题判定是否存在S的一个子集S1，使得∑x = t。(x属于S1)
1 子集和问题的指数时间算法
int exactSubsetSum (S,t)
{
int n=|S|；
L[0]={0}；
for (int i=1；i<=n；i++) {
L[i]=mergeLists(L[i-1],L[i-1]+S[i])；
删去L[i]中超过t的元素；
}
return max(L[n])；
}
算法以集合S={x1，x2，…，xn}和目标值t作为输入。算法中用到将2个有序表L1和L2合并成为一个新的有序表的算法mergeLists(L1,L2)。
2 子集和问题的完全多项式时间近似格式
基于算法exactSubsetSum，通过对表L[i]作适当的修整建立一个子集和问题的完全多项式时间近似格式。
在对表L[i]进行修整时，用到一个修整参数δ，0<δ<1。用参数δ修整一个表L是指从L中删去尽可能多的元素，使得每一个从L中删去的元素y，都有一个修整后的表L1中的元素z满足(1-δ)y≤z≤y。可以将z看作是被删去元素y在修整后的新表L1中的代表。
举例：若δ=0.1，且L=〈10,11,12,15,20,21,22,23,24,29〉，则用δ对L进行修整后得到L1=〈10，12，15，20，23，29〉。其中被删去的数11由10来代表，21和22由20来代表，24由23来代表。
对有序表L修整算法
List trim(L,δ)
{ int m=|L|；
L1=〈L[1]〉；
int last=L[1]；
for (int i=2；i<=m；i++) {
if (last<(1-δ)*L[i]) {
将L[i]加入表L1的尾部；
last=L[i]；
}
return L1；
}
子集和问题近似格式
int approxSubsetSum(S,t,ε)
{ n=|S|；
L[0]=〈0〉；
for (int i=1；i<=n；i++) {
L[i]=Merge-Lists(L[i-1],
L[i-1]+S[i])；
L[i]=Trim(L[i],ε/n)；
删去L[i]中超过t的元素；
}
return max(L[n])；
}

‘贰’ 并集和交集的公式是什么

交集？并集？

你还记得高中数学的第一课吗？讲的是集合，具体定义去网络，里面有两个运算法则：交集和并集。也许你当时觉得很容易，那么今天还是回头想想它在讲什么。

一、两个集合

一切运算都是两个相对的集合间的关系法则，既然是高中数学，那么就略谈一下教育，其实很多人会说“你考好了说明学好了”，然而我想说的是考试和教学是两个集合。

我们看看中国过去的八股文，包括今天的高考，受到那么多诟病，但是为什么还是继续这么做？因为相关部门不知道，无作为？我觉得要是从另外一个角度看，考试作为一种人才选拔的工具，那选拔什么样的人呢？是见多识广、才华横溢的人；还是那些面对一个目标，能持之以恒地找方法达成，坐得住、能下功夫的人呢？

不好意思，答案很可能是后者。

现在很多创业公司都有这样的体会。招人的时候，他们往往不是倾向于招那些有经验的人，而倾向学习能力好、沟通能力强、对自己要求严、有自我驱动能力的人。因为创业公司本来做的就是全新的事情，经验这个东西是有益还是有害，说不清楚。但是面对任何新的情况，都能找到方法、诉诸行动、不丢目标的人，才是创业公司需要的。前一阵还有一位创业公司的创始人跟我说，他发现优秀的大学生，比行业里的老鸟好用。

这种优秀的人，不管面对什么样的题目，哪怕是八股文，也一样可以坐得住、下苦功，最后考出好成绩。这样的人走入仕途，面对自己不熟悉的任务，也一样会表现优秀。事实上，明清两代那么多能人都是靠八股文选拔出来的，比如我们熟悉的王阳明和曾国藩。

再回头来说我们的高考。

这几年，高考的发展趋势和八股文正好相反的，这也是很多人呼吁和推动的结果。各地高考越来越强调地方特色，越来越多地考核学生的所谓“综合素质”。这种发展方向看似正确，但是也有值得反思的地方。

首先，中国是一个大国，各地情况差异巨大，社会阶层也差异巨大。只有坚持全国的统一性，才能确保人才通过高考在全国范围内的流动和交流，维持整个国家的内在联系和国家认同。不夸张地说，如果高考的全国统一性消失了，中国各个地方的内在联系会被严重削弱。

我们不能把高考仅仅看作是教育的一个环节，高考是国家治理中的关键，事关国家的完整统一和治理水平。

其次，虽然不必恢复到八股文那样死板的形式，但高考仍然要尽量维持简单、明晰的考试内容和形式。一言以蔽之，永远要确保，学生只靠几本教科书、只比拼硬功夫、笨功夫就能取得好成绩。

和科举一样，高考不是教育工具，高考是人才选择的工具。它把各个社会阶层里奋发向上，能坐得住、下苦功夫的人挑选出来，保持这个社会的活力和公平。这才是高考在当前中国社会的真实作用。

然而，所谓教育则是一种能力的培养，一种思维模式的锻炼，比如我们讲集合，你不光会做题还要会应用，比如将学习数学思维和考试分开来，当然它们之间有交集，就是你既能坐下来刷题总结，又能进行发散和转化，你要既能学好集合又能考好集合这就是交集，而你只是明白自己要好好学习并且考试优异这就是并集。其实大多数人在看问题的时候喜欢用并集，这样比较省事，也符合原始的认知方式，然而今天这种方式与时代有所不匹配啦，这种人就是那些现在边缘只求安全感，却不愿多向集合内多走一步深入了解的人。我们在许多问题上可以有所区分，比如人工智能就是未来一切的引导？关系问题一定是其中一个人有问题或者两个人有问题？

二、人工智能就是人类的全部模拟？

这个的答案明显是否定的，人工智能是完全通过算法运行的，这些算法都来自于各个学科的模型计算，你去翻翻书，所以学科都有一个所谓的理想假设，这个假设通俗的讲就是，如果世界只有XX学科来指导运行的话。所以人工智能可以模拟任意学科，但是这是不同的集合，交集并不能完全模拟，对于这个问题，很多人认为只要融合了那么交集自然呈现啊，其实不然。举个例子，一些有经验的心理咨询师在处理感情纠葛问题时，会说他面对的是三个人，夫妻双方和他们的关系，而关系就是交集的结果，所以关系问题不一定是个人或者两个人的问题导致，也有可能是他们的交集，也就是产生的关系导致。再者人工智能更偏向科学，而科学思维和技术仅仅是社会中的小部分，还有大部分的人性，也就是社会科学，例如人工智能的围棋站，输的那一局就是输在人性上，所以任何复杂问题回答时，可以考虑下是否存在两个及以上集合，因为可能存在第三者。（上述问题因本文需求，不多做拓展）这样一个是非问题只有两个答案，却可能有三层认知。

三、认知三级跳

最近中子星的新闻应该都看过了，那么问个看问题，宇宙是有限的还是无限的？如果回答宇宙是有限大的，那说明这个人具备了一定的科学素养。如果他回答宇宙是无限大的，那就有两种可能。一种可能是这个人对现代科学一无所知；另一种可能，却是他对天体物理学的最新进展非常了解。

第一层，无限大，从小就知道宇宙浩瀚无边，没有天边，所以无限大。

第二层，有限大，知道宇宙大爆炸，就知道宇宙是个正在被吹大得气球，不管怎么变大，气球总还是有边界的，于是有限大。

第三层，无限大，根据2013最新发现，宇宙质能比例系数为1±0.004，以及宇宙背景辐射的数据，证明在欧几里得空间内，宇宙是一个平面，无限延伸。

那么又会出现一个特别有意思的情况，二八理论，如果去统计下会发现中间层的人会有80%，所以当你和很多别人的观点一样的时候就要警惕啦，你是不是中间层？你也许离出现集合只有一步，而你却沾沾自喜。

同样的事情我们看看对朋友圈的认识，最早用的时候，很多人不习惯的，认为不好所以希望不要有。当发现里面信息多样化，被设计吸引后，几乎大多数人都爱它。而像我自从写出那篇朋友圈是黑暗森林后，至今朋友圈没看过，而我并没有过不下去，或者对我的生活学习工作没有太大影响，那我还去看了干嘛，花去巨大的时间成本，却基本没有收益啊。

‘叁’ 算法的子集和数问题

回溯算法设计2008-05-29 10:15 P.M.[实验目的]

1. 掌握回溯法解题的基本思想；

2. 掌握回溯算法的设计方法；

3. 针对子集和数问题，熟练掌握回溯递归算法、迭代算法的设计与实现。

[预习要求]

1. 认真阅读教材或参考书, 掌握回溯法解题的基本思想, 算法的抽象控制策略；

2. 了解子集和数问题及解向量的定长和变长状态空间表示；

3. 针对解向量的定长表示, 设计状态空间树节点扩展的规范(限界)函数及实现方法；

4. 分析深度优先扩展状态空间树节点或回溯的条件；

5. 分析和设计生成解向量各分量可选值的实现方法；

6. 设计和编制回溯算法的递归和迭代程序。

[参考数据类型或变量]

float s; // 表示有可能抵达答案节点的子路径上的元素之和；

float r; // 尚未测试的剩余集合元素之和；

float w[n]; // 存储原始集合的n个元素, 根据问题实例初始化；

int x[n]; // 定长表示的解向量, 各元素初始值为0；

[参考子程序接口与功能描述]

void RecursiveSubset(float s, float r, int k)

功能: 针对问题实例的递归回溯算法。

void IterativeSubset(int m)

功能: 针对问题实例的迭代回溯算法。

void InitializeInstanse(void)

功能: 问题实例的初始化函数, 初始化子集和数M , w, x向量, s, r。

[实验步骤]

1. 录入、修改并测试你的程序，直至正确为止；

2. 针对问题实例，实录运行时的输入、输出界面；

3. 将你的程序和实录的界面存盘备用。

[实验报告要求]

1. 阐述实验目的和实验内容；

2. 提交模块化的实验程序源代码；

3. 简述程序的测试过程，提交实录的输入、输出界面；

4. 鼓励对实验内容展开讨论，鼓励提交思考与练习题的代码和测试结果。

[思考与练习]

1. 试针对解向量的变长表示设计回溯算法，上机测试正确性。

2. 试针对0/1背包问题设计回溯算法，比较与子集和数问题的算法差异。

#include<stdio.h>
#define n 3
float s; /*表示有可能抵达答案节点的子路径上的元素之和；*/
float r; /*尚未测试的剩余集合元素之和；*/
float w[n]={2,3,4}; /*存储原始集合的n个元素, 根据问题实例初始化；*/
int x[n]; /*定长表示的解向量, 各元素初始值为0；*/
int M;
int k;

void RecursiveSubset(float s, float r, int k)/*针对问题实例的递归回溯算法*/
{int i;
x[k-1]=1;
if(s+w[k-1]==M)
{for(i=0;i<n;i++)
printf("%2d",x[i]);
printf("\n");}

else if(((s+r)>=M)&&((s+w[k-1]+w[k]<=M)))
RecursiveSubset(s+w[k-1],r-w[k-1],k+1);
if((s+r-w[k-1]>=M)&&((s+w[k])<=M))
{x[k-1]=0;
RecursiveSubset(s,r-w[k-1],k+1);
}
}
void IterativeSubset(int m)/*针对问题实例的迭代回溯算法*/
{int i;
for(i=0;i<m;i++) x[i]=2;
for(i=k-1;i<n;i++) r+=w[i];
k=1;
while(k>0)
{--x[k-1];
if(x[k-1]==0)
{if((s+r-w[k-1]>=M)&&(s+w[k]<=M))
{s+=x[k-1]*w[k-1];
r-=w[k-1];
k++;
continue;
}
else{
--k;
s-=x[k-1]*w[k-1];
r+=w[k-1];
for(i=k;i<m-1;i++)
x[i]=2;
continue;
}
}
if(s+w[k-1]==M)
for(i=0;i<n;i++)
{printf("%2d",x[i]);}
else if((s+r>=M)&&(s+w[k-1]+w[k]<=M))
{s+=w[k-1];r-=w[k-1];k++;}
}
printf("\n");
}
void InitializeInstanse(void) /*问题实例的初始化函数, 初始化子集和数M , w, x向量, s, r*/
{int i;
printf("Enter M:");
scanf("%d",&M);
for(i=0;i<n;i++)x[i]=0;
for(i=k-1;i<n;i++) r+=w[i];
for(i=0;i<k-2;i++) s+=x[i]*w[i];
}
main()
{InitializeInstanse();
RecursiveSubset(s,r,k);
IterativeSubset(n);
system("pause");