0,1背包问题:我写笔记风格就是想到哪里写哪里,有很多是旧的也没删除,代码内部可能有很多重复的东西,但是保证能运行出最后效果

'''学点高大上的遗传算法''''''首先是Np问题的定义:npc:多项式复杂程度的非确定性问题,首先是基本的0-1背包问题。 ''''''给定N个物品和一个背包，物品i的质量是Wi，其价值位Vi，背包的容量为C，问应该如何选择装入背包的物品，使得转入背包的物品的总价值为最大？ 在选择物品的时候，对每种物品i只有两种选择，即装入背包或不装入背包。不能将物品i装入多次，也不能只装入物品的一部分。因此，该问题被称为0-1背包问题。''''''如果穷举就有2^n个需要测试,很大''''''其实，0-1背包是DP的一个经典实例，可以用动态规划求解。DP求解过程可以这样理解：对于前i件物品，背包剩余容量为j时，所取得的最大价值（此时称为状态3）只依赖于两个状态。状态1：前i-1件物品，背包剩余容量为j。在该状态下，只要不选第i个物品，就可以转换到状态3。状态2：前i-1件物品，背包剩余容量为j-w[i]。在该状态下，选第i个物品，也可以转换到状态3。因为，这里要求最大价值，所以只要从状态1和状态2中选择最大价值较大的一个即可。''''''算法复杂度基本是O(N)'''bag_weight=95800stone=[]#stone[i] means (weight, value)stone.append((100,100))stone.append((200,105))stone.append((300.9,400))stone.append((400.56,900.56))stone.append((500,1000.598))stone=sorted(stone) #default sorted by first column of stone ,very convinientprint (stone)#creat a two-dim list,row i means using the first i stone#column j means the bag_weight'''只想到用递归来写,递推还不知道怎么弄'''#网上说法是不能用递推来写,因为不知道重量的变化,变化太多,不知道要存多少才行.#下面写出打印的最好的石头组合的index,现在是这个问题比较难!!!!!!!!!!!因为递归问题很难区分这次和上次#来的index,反复访问很难弄,下面用函数的双返回值来处理这个问题,但是空间开销也是相当大.目测O(N^2)zuhe=[0]*len(stone)def value(num,tmpbag_weight):      if num==1:            if tmpbag_weight>=stone[0][0]:                                                                            return 100            else:                  return 0      firstcase=0      if tmpbag_weight>=stone[num-1][0]:                      firstcase=0          firstcase+=stone[num-1][1]          firstcase+=value(num-1,tmpbag_weight-stone[num-1][0])      secondcase=value(num-1,tmpbag_weight)            return max(firstcase,secondcase)print (value(len(stone),bag_weight))print (zuhe)###########print ('妈的我居然写出来了55555555')def value(num,tmpbag_weight):      if num==1:            if tmpbag_weight>=stone[0][0]:                                      zuhe=[0]                                      return stone[0][1],zuhe            else:                  return 0,[]      firstcase=0      if tmpbag_weight>=stone[num-1][0]:                      firstcase=0          firstcase+=stone[num-1][1]          a,b=value(num-1,tmpbag_weight-stone[num-1][0])          firstcase+=a      c,d=value(num-1,tmpbag_weight)      secondcase=c      if firstcase>secondcase:        b.append(num-1)        return max(firstcase,secondcase),b      else:        return max(firstcase,secondcase),dprint (value(len(stone),bag_weight))

 2.kmp

'''匹配字符串bf算法'''def search(a,b):#if a in b :return first index else:return None      for i in range(len(b)):       #直接b切片就行了,记住几个常用计数长度更方便       #range[i,i+len(a)] 标示角标从i一直到i+len(a)-1一共len(a)个元素       #切片也类似b[i:i+len(a)]也表示len(a)个元素            if i+len(a)-1==len(b):                  return None            if b[i:i+len(a)]==a:                  return iprint (search('ffg','qfgsdfgsdffg'))'''下面是KMP算法--看毛片算法''''''把复杂度从O(mn)下降到O(m+n)'''#这个写的很详细,KMP还是要从例子的图形里面分析出来.注意next[0]=-1,是一种人为的规定,为了识别,你定义-2也一样.'''http://www.cnblogs.com/yjiyjige/p/3263858.html''''''先学一下c语言里面的++''''''首先要说：a++ = a 和 ++a = a + 1 并不是两个合法的语句。这两个式子是说 a++ 的值就是 a 的值，而 ++a 的值等于 a+1。 注意：我说的是++a和a++的值。你的这两个表达式不合法！在C语言中前置和后置自增运算符返回的结果是右值，不能放在等号左侧。顺便提一下：在C++中，前置自增的结果是左值，可以放在等号左侧。1.int main() {  int b=0;  int a=3;  ++a=b;  a+=1;  return 0;}   答案a是12.int main() {  int b=0;  int a=3;  b=++a;  a+=1;  return 0;}  答案a是53.int main() {  int b=0;  int a=3;  a++=b;  a+=1;  return 0;}  第四句话不合法,无法运行'''#c++什么鬼#要先写获取next数组这个函数#先用暴力方法实现next数组的求法.'''理解:待处理数组,也就是我们要配出的字符串,比如一个长串里面找一个短的串,那么待处理数组就是这个短的设为p''''''p=abcaab  那么我们的next数组就是-1,0,0,0,1,1next[i]的招法是符合下面条件的最大的index1.next[i]
      
       len(b)-1:                  return None            if b[i]==a[j]:                  i+=1                  j+=1            else:                  if nextshuzu[j]==-1:                        i+=1                        j=0                  else:                        j=nextshuzu[j]                        print (kmp('43aa','3ht54543aa43a4a6'))print (kmp('1','23'))#效果还不错.#最后应该用动态规划来写next数组了.#http://www.cnblogs.com/yjiyjige/p/3263858.html里面写的真的很详细.#像这种情况，如果你从代码上看应该是这一句：k = next[k];为什么是这样子？你看下面应该就明白了。#上面这句话在博客里面的说没说完,其实k=next[k]这个吊代码,把2次匹配next给用一个代码写明白了,确实叼.#下面只需要改成python实现即可.def next_true(a):      shuchu=[]      shuchu.append(-1)      j=0      k=-1      while (j
      

 3.遗传算法解背包问题,一写一个晚上没了,干了200行,我理解是这东西就是个类似随机查找的东西,本质很low,但是实用性强,有点像神经网落,普世通用性强.描述性强

缺陷当然是慢!!写写还挺有意思,复习了很多的random函数的使用.这东西不推荐手写大型的,因为有库直接能调用遗传算法.当然现在还有遗传加神经网络的综合体,有点

强.

'''学点高大上的遗传算法'''import randomprint (random.randint(10, 11))#python 的这个随机正数是包含收尾的,这点要注意.很特俗'''首先是Np问题的定义:npc:多项式复杂程度的非确定性问题,首先是基本的0-1背包问题。 ''''''给定N个物品和一个背包，物品i的质量是Wi，其价值位Vi，背包的容量为C，问应该如何选择装入背包的物品，使得转入背包的物品的总价值为最大？ 在选择物品的时候，对每种物品i只有两种选择，即装入背包或不装入背包。不能将物品i装入多次，也不能只装入物品的一部分。因此，该问题被称为0-1背包问题。''''''如果穷举就有2^n个需要测试,很大''''''其实，0-1背包是DP的一个经典实例，可以用动态规划求解。DP求解过程可以这样理解：对于前i件物品，背包剩余容量为j时，所取得的最大价值（此时称为状态3）只依赖于两个状态。状态1：前i-1件物品，背包剩余容量为j。在该状态下，只要不选第i个物品，就可以转换到状态3。状态2：前i-1件物品，背包剩余容量为j-w[i]。在该状态下，选第i个物品，也可以转换到状态3。因为，这里要求最大价值，所以只要从状态1和状态2中选择最大价值较大的一个即可。''''''算法复杂度基本是O(N)'''bag_weight=1200stone=[]stone.append((100,100))stone.append((200,105))stone.append((300,400))stone.append((400,900))stone.append((500,1000))#　举个例子，使用遗传算法解决“0-1背包问题”的思路：0-1背包的解可以编码为一串0-1#字符串（0：不取，1：取） ；首先，随机产生M个0-1字符串，然后评价这些0-1字#符串作为0-1背包问题的解的优劣；然后，随机选择一些字符串通过交叉、突变等操作产生下#一代的M个字符串，而且#较优的解被选中的概率要比较高。这样经过G代的进化后就可能会产生#出0-1背包问题的一个“近似最优解”。#遗传算法的问题'''1.编码:需要将问题的解编码成字符串的形式才能使用遗传算法。最简单的一种编码方式是二进制编码，即将问题的解编码成二进制位数组的形式。例如，问题的解是整数，那么可以将其编码成二进制位数组的形式。将0-1字符串作为0-1背包问题的解就属于二进制编码。2.遗传算法有3个最基本的操作：选择，交叉，变异。下面处理第一个选择问题:1.问题:有n个物体,他们被选择的概率是p1,...pn.和为1.求一个函数每次根据这个概率随机出一个物体.这个用random(0,1)函数随便写很简单--他们管这个叫轮盘赌算法下面我定义他是rws(RouletteWheel Selection )函数.第二个问题交叉:http://www.cnblogs.com/heaad/archive/2010/12/23/1914725.html这里面只写了原理没有实现,最后用一个库包来实现的,我打算还是自己手写一次根据他里面的思想,手动实现遗传算法.原理写下来:交叉(Crossover)：2条染色体交换部分基因，来构造下一代的2条新的染色体。例如：变异(Mutation)：在繁殖过程，新产生的染色体中的基因会以一定的概率出错，称为变异。变异发生的概率记为Pm 。例如：'''import randoma=[0.1,0.2,0.3,0.4]#物体被选择的概率,这个概率就是这个物体的效果函数def rws(a):      #生成累加概率            b=random.random()      for i in range(len(a)):           j=(sum(a[:i+1]))           if b
      
       bag_weight:            value/=4      return valuedef all_value(a_all):      b=[]       for i in range(len(a_all)):            b.append(value_of_pick(a_all[i]))      return b#下面开始跑遗传a_all=init(10)all_the_value=all_value(a_all)he=sum(all_the_value)for i in range(len(all_the_value)):     all_the_value[i]/=he#上步是归一化#先选2个,然后进化for i in range(50):#进化50次  first=rws(all_the_value)  second=rws(all_the_value)  #这里假设自己和自己也能繁殖..  a,b=crossover_and_mutation(a_all[first],a_all[second],0.3)  a_all.append(a)  a_all.append(b)  all_the_value=all_value(a_all)  he=sum(all_the_value)  for i in range(len(all_the_value)):      all_the_value[i]/=hejieguo=(all_value(a_all))print (max(jieguo))#下面我们找到这个答案的具体的pick方法.index_final=np.argmax(np.array(jieguo))print (a_all[index_final])print ('总结取法',end=''),print(a_all[index_final],end=''),print('价值',end=''),print(max(jieguo))
      

 4.hash表数据结构的实现

'''Hash表''''''核心就是hash函数的设计：特点：在构造Hash函数时应尽量考虑关键字的分布特点来设计函数使得Hash地址随机均匀地分布在整个地址空间当中。1)直接定址法　　取关键字或者关键字的某个线性函数为Hash地址，即address(key)=a*key+b;如知道学生的学号从2NoneNoneNone开始，最大为4NoneNoneNone，则可以将address(key)=key-2NoneNoneNone作为Hash地址。2)平方取中法　　对关键字进行平方运算，然后取结果的中间几位作为Hash地址。假如有以下关键字序列{
     421，423，436}，平方之后的结果为{
    177241，178929，19NoneNone96}，那么可以取{
    72，89，NoneNone}作为Hash地址。3)折叠法　　将关键字拆分成几部分，然后将这几部分组合在一起，以特定的方式进行转化形成Hash地址。假如知道图书的ISBN号为89None3-241-23，可以将address(key)=89+None3+24+12+3作为Hash地址。4)除留取余法　　如果知道Hash表的最大长度为m，可以取不大于m的最大质数p，然后对关键字进行取余运算，address(key)=key%p。　　在这里p的选取非常关键，p选择的好的话，能够最大程度地减少冲突，p一般取不大于m的最大质数。''''''5.Hash表的优缺点　　Hash表存在的优点显而易见，能够在常数级的时间复杂度上进行查找，并且插入数据和删除数据比较容易。但是它也有某些缺点，比如不支持排序，一般比用线性表存储需要更多的空间，并且记录的关键字不能重复。'''a=[1,2,3,4,51,2,3,4,51,2,3,4,551,2,3,4,551,2,3,4,551,2,3,4,551,2,3,4,551,2,3,4,5]class hashnode():    def __init__(self,data):     self.data=data;     self.next=None#下面写的是取mod的方法：一般除数取比len(表)小的最大素数。#获取除数import mathb=len(a)if b==1:    c=1if b==2:    c=2if b==3:    c=2if b>3: def sushu(b):  for i in range(b-1,2,-1):     k=None          for j in range(2,int(math.sqrt(i))+2):                  if i%j==None:             break                      if j==int(math.sqrt(i))+1:          k=1       if k==1:           return i c=sushu(b)#除数就是c #下面建立hash 表 hashlist=[None]*c print (c) for i in range(len(a)):     hashtmp=a[i]%c          if hashlist[hashtmp]==None:         hashlist[hashtmp]=hashnode(a[i])     else:        head=hashlist[hashtmp]        while 1:                        if  head.next!=None:                head=head.next                continue            else:                head.next=hashnode(a[i])                breakprint (hashlist[2].next.next.data)print (66666666)#然后添加元素。直接复制上面的部分代码即可。都类似的。def add(one):  hashtmp=one%c  if hashlist[hashtmp]==None:     hashlist[hashtmp]=hashnode(one) else:    head=hashlist[hashtmp]    while 1:                if  head.next!=None:            head=head.next            continue        else:            head.next=hashnode(one)            breakadd(11)print (hashlist[0])def delme(two): hashtmp=two%c  if hashlist[hashtmp]==None:     pass else:    head=hashlist[hashtmp]    while 1:               if head.data==two:           head.data=None       if head.next!=None:           head=head.next           continue       if head.next==None:           breakdelme(11)print (hashlist[0])#下面写查询,这个写的是全部查询，找到所有等于a的hashlist里面的元素的个数def search(a):    hashtmp=a%c    b=0    head=hashlist[hashtmp]    while 1:        if head.data==a:            b+=1        if head.next!=None:            head=head.next            continue        if head.next==None:            break    return bprint (search(2))#曾，删，改，查，建立，都有了#下面写个修改。这个修改貌似很多数据结构不写这个方法。def change(two,three): hashtmp=two%c  if hashlist[hashtmp]==None:     pass else:    head=hashlist[hashtmp]    while 1:               if head.data==two:           head.data=three       if head.next!=None:           head=head.next           continue       if head.next==None:           breakchange(2,3)#因为把所有的2都改成了3所以下面的搜索会变成0print (search(2))print (search(3))  #其实这个改有很大问题，因为他没有改变hash的东西，是否需要重新建立改完东西的hash索引，这个#是需要讨论的，但是本质都不难。这里面写的change只是把原来放2的地方数据都改成了3,。所以你找3还是找不到新修改#的那8个3，还是最开始的那8个3.ps：出事数据里面是8个2 ，8个3的。

 5.位图法的实现

##位图大发好神奇''' 1、给40亿个不重复的unsigned int的整数，没排过序的，然后再给一个数，如何快速判断这个数是否在那40亿个数当中　　首先，将这40亿个数字存储到bitmap中，然后对于给出的数，判断是否在bitmap中即可。位图和位向量所谓位向量法，其实就是使用一串二进制串来表示一组数字集合的方法。比如，我们知道一个byte = 8bit，表示成二进制串就是：00000000.这里我们就得到了八个可用的符号位，假如我们作如下规定1）符号位为1的，说明存在于我们的数字集合中2）符号位为0的，说明不在我们的数字集合中那么，二进制串01010101，表示的数字集合为{
     1,3,5,7} （注意，计算机通常都是从0开始计算的）。。我们知道位图的数据结构就是一个数组，而位图的操作（算法）基本依赖于下面3个元操作set_bit(char x, int n); //将x的第n位置1，可以通过x |= (1 << n)来实现clr_bit(char x, int n); //将x的第n位清0，可以通过x &= ~(1 << n)来实现get_bit(char x, int n); //取出x的第n位的值，可以通过(x >> n) & 1来实现'''#下面用python手动实现。python所有的数本质都是2进制，可以直接用位运算。#举一个例子，一个集合里面有数字1,3,5 那么我们用二进制010101 来表示。也就是第一个0表示没有数字0，然后1表示#有数字1，0表示没有2, 1表示有数字3, 下一位0又表示没有数字4，最后一个1表示有数字5.#这样用一个数字就表示了函数数字1,3,5这个信息了。问题是python的二进制是从右边开始算的。所以我们再反转一下#用101010来表示1,3,5存在这个信息就行了。b=[1,3,4,5,19,8]def init(a):#首先建立第一个数字存在的信息    return 1<
      
       =1:        chushihua=chushihua |(1<
       
        >a) &1print (search(chushihua,8))print (search(chushihua,19))print (search(chushihua,9))print (search(chushihua,20))#成功解决这个问题。#还有一个删除函数。比如我有一个操作把所有等于8的数从集合中删除。下面来给他写出来#思路也不难，比如删除8：我就做一个011111111，然后跟chushihua取交就完了。这地方有那么一点点的复杂。trickdef delme(chushihua,a):    chushihua=(chushihua &(~(1<
        
         =1:        chushihua=chushihua |(1<
        
       
      

 6.最长公共子序列问题

'''最长公共子序列：显然动态规划''''''经过画图分析，显然是2阶动态规划问题''''''设f(a,b,i,j)表示a从0到i的子串，和b从0到j的子串这2个子串的最长公共序列的长度''''''那么f(a,b,i,j)是从f(a,b,i-1,j),f(a,b,i,j-1),f(a,b,i-1,j-1)里面开发出来的'''#具体直接写代码。def f(a,b,i,j):      if i==0:            if a[0] in b:                  return 1            else:                  return 0      if j==0:            if b[0] in a:                  return 1            else:                  return 0      case1=case2=case3=0      if a[i]==b[j]:            case1=1+f(a,b,i-1,j-1)      if a[i]!=b[j]:            case2=f(a,b,i-1,j)            case3=f(a,b,i,j-1)      return max(case1,case2,case3)a='343242dsfd'b='dsfds'print (f(a,b,len(a)-1,len(b)-1))#上面很简单，3分钟搞定。男的是要把这个解解出来，而不仅仅是输出一个数字。#这个跟背包问题很像，递归里面开数组。不是太好写。# 下面开始尝试。keyword:多返回值函数def f(a,b,i,j):      if i==0:            if a[0] in b:                  return 1,a[0]            else:                  return 0,''      if j==0:            if b[0] in a:                  return 1,b[0]            else:                  return 0,''      case1=case2=case3=0      if a[i]==b[j]:            case1=1+f(a,b,i-1,j-1)[0]            case1_data=f(a,b,i-1,j-1)[1]+a[i]      if a[i]!=b[j]:            case2=f(a,b,i-1,j)[0]            case2_data=f(a,b,i-1,j)[1]            case3=f(a,b,i,j-1)[0]            case3_data=f(a,b,i,j-1)[1]#如果有相同长度的解，应该返回最前面的。那么case2和case3如果相同呢？？？？？？？？                                                   #我认为这个是一个相当男的bug了，弄点诡异数据来测一测。                                                  #然而经过我长时间的分析，这个bug其实是没有的，具体很复杂，不容易说明白，                                                   #结论我先说一下，就是这个代码      if case1>case2 and case1>case3:            return case1,case1_data      if case2>=case1 and case2>=case3:   #这个代码case2》=case3为什么这么写可以，也就是说如果相等，我还是                                                                 #只需要返回case2即可，舍弃case3.我尝试一下说明白这个取舍问题。                                                               #道理就是你的这种取舍，考虑的前提就是case2里面最后一个元素被使用到了，然而                                                             #你如果发生bug那么就必然发生这种情况，下面再让i+1，j+1后，如果用case3里面的情况                                                           #会添加一个元素得到的长度比case2里面的长。但是这是不可能的，原因就是上一步                                                        #已经保证了case2里面最后一个元素使用过了。总之很难说清楚的东西。            return case2,case2_data      if case3>=case1 and case3>=case2:            return case3,case3_data      a='babax'b='bbaxy'print (f(a,b,len(a)-1,len(b)-1))

 7.最长公共子串

'''最长公共子串''''''也是动态规划'''def com(a,b,i,j): #得到a，b的公共子串并且子串以a[i]和b[j]作为结尾的长度,                         #然后把他们保存起来用下面的get函数，然后我们再取这个矩阵最大的就行了    if i==0:        if b[j]==a[i]:            return 1        else:            return 0    if j==0:        if a[i]==b[j]:            return 1        else:            return 0    if a[i]==b[j]:        return com(a,b,i-1,j-1)+1    else:        return 0def get(a,b):    save=[]    for i in range(len(a)):        for j in range(len(b)):             save.append(com(a,b,i,j))    return max(save)print (get('aa3232','aaa783232'))#效果还不错。#下面还是继续写，把这个最长子串的组合写出来。    def com(a,b,i,j): #得到a，b的公共子串并且子串以a[i]和b[j]作为结尾的长度,                         #然后把他们保存起来用下面的get函数，然后我们再取这个矩阵最大的就行了    if i==0:        if b[j]==a[i]:            return 1,a[i]        else:            return 0,''    if j==0:        if a[i]==b[j]:            return 1,a[i]        else:            return 0,''    if a[i]==b[j]:        return com(a,b,i-1,j-1)[0]+1,com(a,b,i-1,j-1)[1]+a[i]    else:        return 0,''def get(a,b):    save=[]    for i in range(len(a)):        for j in range(len(b)):             save.append(com(a,b,i,j))    return max(save)print (get('aa3232','aaa783232'))#一样轻松写出。

 8.全域散列法,随机hash的思想

 

'''全域散列,随机hash技术''''''全域散列法在执行的开始时,就从一组精心设计的函数总,随机的选择一个作为散列函数,随机化保证了没有哪一个输入会导致最坏性能情况的发生.''''''构造这个函数族很复杂,也不是非常复杂:原范围是p,分类后的曹数是m,也就是把p范围内的数都分布到m个曹当中h(k)_(a,b)=((ak+b)modp)modm那么因为p,m去定.a跑遍1到p-1,b跑遍1到p就构造了p(p-1)这么多个函数.他的性质是Pr(h(k)_(a,b)=h(k)_(a,b)).'''

 9.二叉搜索树:

#coding:utf-8#首先是二叉搜索树的定义:'''若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。''''''二叉搜索树''''''二叉搜索树里面的元素都是不重复的所以当插入一个元素时候先搜索他是否在树里面,如果在就不插入了,不果不在就插入'''class node():        def __init__(self,data):            self.left=None            self.right=None            self.data=data#不能把类写在另一个类里面class ercha():        def __init__(self):        self.head=node(None)    def input(self,a):        old_head=self.head        while 1:                          if self.head.data==None:                 self.head.data=a                 self.head=old_head                 return             if self.chazhao(a)==None:                 if a
      
       self.head.data and self.head.right==None:                      self.head.right=node(a)                      self.head=old_head                      return                 if a>self.head.data and self.head.right!=None:                            self.head=self.head.right                            continue                                       def chazhao(self,a):     old_head=self.head     while 1:        if self.head==None:                   self.head=old_head                   return None        if a==self.head.data:            new_head=self.head            self.head=old_head            return new_head        if a>self.head.data:                   self.head=self.head.right                   continue        if a
      

 

#自己写的不对,还是贴个别人的吧class TreeNode:    def __init__(self,val):        self.val=val;        self.left=None;        self.right=None;def insert(root,val):    if root is None:        root=TreeNode(val);    else:        if val
      
       root.val:            root.right=insert(root.right,val);      return root;def query(root,val):    if root is None:        return ;    if root.val is val:        return 1;    if root.val 
       
        root.val:        return delnum(root.right,val);    else:                                             # 删除要区分左右孩子是否为空的情况        if(root.left and root.right):                        tmp=finmin(root.right);             #找到后继结点            root.val=tmp.val;            root.right=delnum(root.right,val);    #实际删除的是这个后继结点                    else:            if root.left is None:                root=root.right;            elif root.right is None:                root=root.left;    return root;                                #測试代码            root=TreeNode(3);root=insert(root,2);root=insert(root,1);root=insert(root,4);#print query(root,3);print (query(root,1))root=delnum(root,1)print (query(root,1))