- 2024-02-28特征方程法解通项公式
本质是母函数的推导形式。不是很会,可能会了母函数之后回来补坑。先来写一个例子。我们有递推式\(a_n=a_{n-1}+a_{n-2}\)。我们仿照这个递推式写出一个方程\(x^2=x+1\)。解得\(x_1=\frac{1+\sqrt5}{2}\),\(x2=\frac{1-\sqrt5}{2}\)。于是得\(a_n=yx_1^n+zx_2^n=y(\frac{1+
- 2023-05-01蛮力法解01背包问题
#include<iostream>usingnamespacestd;structthing{intweight;//物品重量intvalue;//物品价值intnumber;//物品序号};thingthings[10];//假设最多有10个物品intthingsCount;//物品数量intbagSize;//背包容量intmaxTotalValue;//最大总重量
- 2023-05-01回溯法解n皇后问题
#include<iostream>usingnamespacestd;#defineMAX21intarr[MAX];//arr[i]=k,表示在第i行的第k个位置放置一个皇后intsum;//计数解的个数intn;//记录几行几列boolcmp(introw,intcol){//当前行和列for(inti=1;i<row;i++){if(col==ar
- 2023-05-01回溯法解工作分配问题
#include<iostream>usingnamespacestd;inta[100][100],sum=0,minn=2147483647,i,j,n;intb[100];voiddfs(intdep){intr;for(r=1;r<=n;++r)//dep表示第几个人,r表示工作if(!b[r])//如果第r件工作没有被选择{
- 2023-05-01分支限界法解01背包问题
#include<iostream>usingnamespacestd;#defineMAX100structNode{intisVisit;//记录节点是否被扩展doublew;doublev;intlevel;//记录节点所在的层次doubleub;//上界Node*parent;//父节点};doublemaxValue=0;Node*PT[MAX
- 2023-05-01分支限界法解TSP问题
#include<iostream>#include<queue>#defineINF1e7#defineMAX100usingnamespacestd;intm[MAX][MAX];//存储城市间的代价intbestPath[MAX];//存储最优路径intbestCost=1e7;//存储最小代价intcityNumber;//城市数目//排列树的节点定义structNode{