一.你对回溯算法的理解
回溯法在问题的解空间树中按照深度优先策略从根结点搜解空间树,在剪枝函数判断后再回溯到祖先结点,所有子树被搜索到才结束。
二.请说明“子集和”问题的解空间结构和约束函数
运用深度优先方法,子集此处相当于序列,遍历所有剪枝后可能的情况,思想类似0-1背包;
1 void dfs(int k,int j,int l) 2 { 3 if(l==m) 4 { 5 for(int i=0;i<j;i++) 6 { 7 cout<<ans[i]<<" "; 8 } 9 chu=1; 10 return; 11 } 12 if((k==n||l+sum[k]<m||l+minn[k]>m)) 13 return; 14 15 if(chu==1) 16 return; 17 if(l+a[k]<=m) 18 { 19 ans[j]=a[k]; 20 dfs(k+1,j+1,l+a[k]); 21 } 22 dfs(k+1,j,l); 23 }
剪枝部分从12行即开始。
三.请说明在本章学习过程中遇到的问题及结对编程的情况
出现了剪枝函数考虑不全导致有些时候超时,以及写main函数时考虑较久的问题。