有哪些信誉好的足球投注网站专题-吕梁.pptVIP

有哪些信誉好的足球投注网站专题 讲课内容 DFS 剪枝 IDA* BFS DFS 概念 图的遍历：过程简要来说是对每一个可能的分支路径深入到不能再深入为止,而且每个节点只能访问一次. 递归实现 例1 有n个物品，每个物品都有一个容量值Wi,一个容量为V的背包。问最多能放多少容量的物品？ 题解 节点所代表的状态：某种可行的方案 代码 void dfs(int k,double sum){ int i,j; if (kn){ if (sum=V) ans=max(ans,sum)); return; } dfs(k+1,sum); dfs(k+1,sum+a[k]); } Xdoj1010-素数环问题 有一个由n个数字相连组成的圆环（n20），组成圆环的数字分别为1，2，3...n-1，n.要求每两个相邻元素的和为素数。（注意：第一个元素始终为1）。? 题解 每个位置都去枚举要放的那一个数，当然得保证每个数字只用一次 代码 void dfs(int k){ if (kn){ if (isprime(a[1]+a[n])){ output(); } return; } for (i=2;i=n;i++){ if (!f[i]isprime[a[k-1]+i]){ a[k]=i; f[k]=1; dfs(k+1); f[k]=0; } } } 剪枝 搜到“无用”的状态就没必要往下搜了 思考一下上两个例题可以剪枝的地方 poj1011 Sticks 给你一些小木棒，长度不同，最后要拼成n个长度相同的长木棒，并且使n最大 题解 迭代：从小到大枚举长棒长度 剪枝 1、状态的选择，一根根长木棒的拼凑 2、从大到小的排放小木棒 3、长度相同的没必要再枚举一次 代码 #includestdio.h #includestring.h int n,a[70],k,f[70],len; void dfs(int t,int sum,int num) { int i,pre=-1; if (numk) {kai=1;return;} if (sum==len) dfs(1,0,num+1); else { for (i=t;i=n;i++) if (!f[i] a[i]!=pre sum+a[i]=len) { pre=a[i]; f[i]=1; dfs(i+1,sum+a[i],num); f[i]=0; if (t==1|| kai) return; } } } void paixu() { int i,j,t; for (i=1;in;i++) for (j=i+1;j=n;j++) if (a[i]a[j]) { t=a[i];a[i]=a[j];a[j]=t; } } int main() { int i,s,j; scanf(%d,n); while (n!=0) { s=0; for (i=1;i=n;i++) { scanf(%d,a[i]); s=s+a[i]; } paixu(); for (i=a[1];i=s;i++) if (s%i==0) { k=s/i; len=i; kai=0; memset(f,0,sizeof(0)); dfs(1,0,1); if (kai) break; } printf(%d\n,i); scanf(%d,n); } return 0; } IDA* 估价函数：当前状态到目标状态的估计值 概念：迭代深搜+估价函数 poj3460 给你一个1-n的排列，比如5 4 3 2 1 ，我们可以把相邻的连续两段数交换位置，问最少的步数使其变成1,2,3...,n 题解 如何构造估价函数：目标状态相邻两数相差1，最多改变3个状态，所以h()=相邻的数差值！=1的个数/3 迭代深搜：跟上一个例题一样 代码 int h(){int i,res=0; for (i=1;in;i++) if (a[i]+1!=a[i+1]) res++; return res/3+(res%3!=0); } BFS 概念：系统地展开并检查图中的所有节点，以找寻结果。 实现方式：队列 走迷宫 一个01矩阵图，0表示可以通过，1表示不能通过，问能不能从左上角走到右下角。 代码 int qx[1000],qy[1000],l,r; int mx[4]={-1,0,1,0}; int my[