devbox
我家小花儿
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

《计算机算法设计与分析》 期末考试整理_计算机算法设计与分析期末考试题

作者：我家小花儿 | 2024-07-27 17:05:33

赞

踩

计算机算法设计与分析期末考试题

因为考试是笔试，所以代码能简则简，非竞赛风~

递归与分治策略

分治法的基本思想

分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。递归地解这些子问题，然后将各子问题的解合并得到原问题的解。

二分搜索技术 O(log⁡n)

能二分查找指定数字下标的前提是数组有序~

思想：搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。

  1. 初始化：将查找区间的起始位置 start 和结束位置 end 分别设置为数组的起始和结束位置。

  2. 循环/递归：在每一步中，计算当前查找区间的中间位置 mid，然后比较中间位置的元素与目标元素的大小关系。

    • 如果中间位置的元素大于目标元素，则更新结束位置为 mid-1，继续在左半部分查找。
    • 如果中间位置的元素小于等于目标元素，则更新起始位置为 mid+1，继续在右半部分查找。
    • 重复上述步骤，直到找到目标元素或者确定目标元素不存在。

  3. 返回结果：如果找到目标元素，则返回其索引；如果不存在，则返回特定值（如 -1）。

时间复杂度：O(log⁡n)

  1. #include<bits/stdc++.h>
  2. const int N=1e5+10;
  3. using namespace std;
  4. int a[N];
  5. int main()
  6. {
  7.     int n,x;
  8.     cin>>n>>x;
  9.     for(int i=1;i<=n;i++) cin>>a[i];
  10.     
  11.     int l=1,r=n,res=-1;
  12.     while(l<=r)
  13.     {
  14.     	int mid=(l+r)/2;
  15.     	if(a[mid]<=x){
  16.     		l=mid+1;
  17.     		res=mid;
  18. 		}else r=mid-1;
  19. 	}
  20. 	
  21. 	if(a[res]!=x) res=-1;
  22. 	cout<<res<<'\n';
  23.     return 0;
  24. }

归并排序 O(nlog⁡n)

思想：将原始数组A[0:n-1]中的元素分成两个大小大致相同的子数组：A[0:n/2]和A[n/2+1:n-1]，分别对这两个子数组单独排序，然后将已排序的两个数组归并成一个含有n个元素的有序数组。（不断地进行二分，直至待排序数组中只剩下一个元素为止，然后不断合并两个排好序的数组段）

  • 分解：将待排序数组分成两个子数组，直到每个子数组的长度为1。

  • 排序：对每个子数组进行排序。递归调用归并排序算法。

  • 合并：合并排好序的子数组，得到一个新的有序数组。

  • 递归：重复以上步骤，直到整个数组排序完成。

时间复杂度：O(nlog⁡n)

787. 归并排序 - AcWing题库

  1. #include<bits/stdc++.h>
  2. const int N=1e5+10;
  3. using namespace std;
  4. int a[N],t[N];
  5. void merge_sort(int l,int r)
  6. {
  7. 	if(l>=r) return ;
  8. 	
  9. 	int mid=(l+r)/2;
  10. 	merge_sort(l,mid);
  11. 	merge_sort(mid+1,r);
  12. 	
  13. 	int l1=l,l2=mid+1;
  14. 	for(int i=l;i<=r;i++)
  15. 	{
  16. 	    if(l2>r||(l1<=mid&&a[l1]<=a[l2])) t[i]=a[l1++];
  17. 	    else t[i]=a[l2++];
  18. 	}
  19. 	for(int i=l;i<=r;i++)
  20. 	{
  21. 	    a[i]=t[i];
  22. 	}
  23. }
  24. int main()
  25. {
  26.     int n;
  27.     cin>>n;
  28.     for(int i=1;i<=n;i++) cin>>a[i];
  29.     merge_sort(1,n);
  30.     for(int i=1;i<=n;i++) cout<<a[i]<<" ";
  31.     return 0;
  32. }

最大子数组O(nlog⁡n)

思想：对于最大子数组和问题，分治算法的基本思想是将数组划分为两个子数组，然后求解左右子数组的最大子数组和，再考虑跨越中间位置的最大子数组和。最后，返回这三个值中的最大值。

  1. 分解：将原始数组划分为两个子数组，分别求解左右子数组的最大子数组和。

  2. 合并：考虑跨越中间位置的最大子数组和。从中间位置向左右两边扩展，分别计算包含中间位置的最大子数组和。

  3. 选择：返回上述三个值中的最大值作为最终结果。

时间复杂度：O(nlog⁡n)

  • 分解步骤：每次分解都需要将数组划分为两个部分，时间复杂度为O(logn)。

  • 合并步骤：对于每一次合并操作，需要线性时间 O(n) 来计算跨越中间位置的最大子数组和。

  • 递归步骤：总共需要进行 O(nlog⁡n) 次递归调用。

P1115 最大子段和 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

  1. #include<bits/stdc++.h>
  2. const int N=2e5+10;
  3. using namespace std;
  4. int a[N],t[N];
  5. int max_array(int l,int r)
  6. {
  7. 	if(l==r) return a[l];
  8. 	
  9. 	int mid=(l+r)/2;
  10. 	int maxleft=max_array(l,mid);
  11. 	int maxright=max_array(mid+1,r);
  12. 	
  13. 	int sum=0,maxl=-1e9,maxr=-1e9;
  14. 	for(int i=mid;i>=l;i--)
  15. 	{
  16. 		sum+=a[i];
  17. 		maxl=max(maxl,sum);
  18. 	}
  19. 	sum=0;
  20. 	for(int i=mid+1;i<=r;i++)
  21. 	{
  22. 		sum+=a[i];
  23. 		maxr=max(maxr,sum);
  24. 	}
  25. 	
  26. 	return max({maxleft,maxright,maxl+maxr});
  27. }
  28. int main()
  29. {
  30.     int n;
  31.     cin>>n;
  32.     for(int i=1;i<=n;i++) cin>>a[i];
  33.     
  34.     cout<<max_array(1,n)<<'\n';
  35.     return 0;
  36. }

动态规划

动态规划基本思想

对于一个能用动态规划解决的问题，一般采用如下思路解决：

  1. 将原问题划分为若干 阶段，每个阶段对应若干个子问题，提取这些子问题的特征（称之为 状态）；
  2. 寻找每一个状态的可能 决策，或者说是各状态间的相互转移方式（用数学的语言描述就是 状态转移方程）。
  3. 按顺序求解每一个阶段的问题。

动态规划算法的基本要素
1 最优子结构
矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。
在分析问题的最优子结构性质时，所用的方法具有普遍性：首先假设由问题的最优解导出的子问题的解不是最优的，然后再设法说明在这个假设下可构造出比原问题最优解更好的解，从而导致矛盾。
利用问题的最优子结构性质，以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。最优子结构是问题能用动态规划算法求解的前提。
注意：同一个问题可以有多种方式刻划它的最优子结构，有些表示方法的求解速度更快（空间占用小，问题的维度低）

2 重叠子问题
递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。这种性质称为子问题的重叠性质。
动态规划算法，对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果。
通常不同的子问题个数随问题的大小呈多项式增长。因此用动态规划算法只需要多项式时间，从而获得较高的解题效率。


思想：
动态规划和分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。
与分治法不同的是，动态规划法中分解得到的子问题不是互相独立的。若用分治法来解这类子问题，分解得到的子问题数目非常多，最后解决原问题需要耗费指数时间。但是这些子问题有很多是相同的，也就是同一个子问题被计算了很多次，不同子问题的数量可能只有多项式量级。
如果我们保存已经解决的子问题的解，需要解相同子问题时找出已经计算出的解，这样可以减少大量重复计算，最终得到多项式时间算法。
经常用一个表来记录所有已解决的子问题的解。不管该子问题以后是否被利用，只要它被计算过，就将其结果填入表中。这就是动态规划的基本思想。具体的动态规划算法多种多样，但它们具有相同的填表格式。

最长公共子序列O(mn)

思想：动态规划求解最长公共子序列的基本思想是构建一个二维数组来保存子问题的解，并利用这些解来推导出原问题的解。

  1. 初始化：构建一个 (m+1)×(n+1)的二维数组，其中第一行和第一列初始化为0。

  2. 递推关系：根据最优子结构性质，利用递推关系计算二维数组中每个位置的值。递推关系通常如下：

    • 如果 A[i]=B[j]，即两个序列的当前字符相等，则 dp[i][j]=dp[i−1][j−1]+1。
    • 如果 A[i]≠B[j]，即两个序列的当前字符不相等，则 dp[i][j]=max⁡(dp[i−1][j],dp[i][j−1])。

  3. 返回结果：二维数组右下角的值即为最长公共子序列的长度。

时间复杂度：O(mn)

897. 最长公共子序列 - AcWing题库

  1. #include<bits/stdc++.h>
  2. const int N=1e3+10;
  3. using namespace std;
  4. int f[N][N];
  5. int main()
  6. {
  7.     int n,m;
  8.     string a,b;
  9.     cin>>n>>m>>a>>b;
  10.     
  11.     a=' '+a;
  12.     b=' '+b;
  13.     
  14.     for(int i=1;i<=n;i++)
  15.     {
  16.     	for(int j=1;j<=m;j++)
  17.     	{
  18.     		f[i][j]=max(f[i-1][j],f[i][j-1]);
  19.     		if(a[i]==b[j]) f[i][j]=max(f[i][j],f[i-1][j-1]+1);
  20. 		}
  21. 	}
  22. 	cout<<f[n][m]<<'\n';
  23. 	
  24.     return 0;
  25. }

01背包O(n*val)

思想：动态规划求解 0-1 背包问题的基本思想是构建一个二维数组 dp，其中 dp[i][w]表示在前 i 个物品中，容量为 w 的背包所能达到的最大价值。

  1. 初始化：构建一个 (n+1)×(W+1) 的二维数组，将第一行和第一列初始化为0，表示背包容量为0或物品数量为0时的情况。

  2. 状态转移：根据 0-1 背包的性质，依次计算每个状态 dp[i][w] 的值。具体的状态转移方程如下：

    dp[i][w]=max⁡(dp[i−1][w],dp[i−1][w−weight[i]]+value[i])

    其中 weight[i] 表示第 i 个物品的重量，value[i]表示第 i 个物品的价值。

  3. 返回结果：最终的结果即为 dp[n][W]，表示在所有物品中，容量为 W 的背包所能达到的最大价值。

时间复杂度：O(n*val)

2. 01背包问题 - AcWing题库

  1. #include<bits/stdc++.h>
  2. const int N=1e3+10;
  3. using namespace std;
  4. int v[N],w[N];
  5. int f[N][N];
  6. int main()
  7. {
  8.     int n,val;
  9. 	cin>>n>>val;
  10. 	for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
  11. 	
  12. 	for(int i=1;i<=n;i++)
  13. 	{
  14. 		for(int j=0;j<=val;j++)
  15. 		{
  16. 			f[i][j]=f[i-1][j];
  17. 			if(j>=v[i]) f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);
  18. 		}
  19. 	}
  20. 	cout<<f[n][val]<<'\n';
  21.     return 0;
  22. }

01背包输出方案

  1. #include<bits/stdc++.h>
  2. const int N=1e3+10;
  3. using ll=long long;
  4.  
  5. int f[N][N],rec[N][N];
  6. int v[N],w[N];
  7. int n,val;
  8.  
  9. void out()
  10. {
  11.     int c=val;
  12.     for(int i=n;i>=1;i--)
  13.     {
  14.         if(rec[i][c]==1)
  15.         {
  16.             std::cout<<"选择商品"<<i<<'\n';
  17.             c-=v[i];
  18.         }
  19.     }
  20. }
  21. void solve()
  22. {
  23.     std::cin>>n>>val;
  24.     for(int i=1;i<=n;i++)
  25.     {
  26.         std::cin>>v[i]>>w[i];
  27.     }
  28.  
  29.     for(int i=1;i<=n;i++)
  30.     {
  31.         for(int j=0;j<=val;j++)
  32.         {
  33.             if( v[i] <= j && w[i] + f[i-1][j-v[i]] > f[i-1][j] )
  34.             {
  35.                 f[i][j]=w[i]+f[i-1][j-v[i]];
  36.                 rec[i][j]=1;
  37.             }else{
  38.                 f[i][j]=f[i-1][j];
  39.                 rec[i][j]=0;
  40.             }
  41.         }
  42.     }
  43.     out();
  44.     std::cout<<f[n][val]<<'\n';
  45. }
  46. signed main()
  47. {
  48.     int t=1;
  49.     //std::cin>>t;
  50.     while(t--)
  51.     {
  52.         solve();
  53.     }
  54.     return 0;
  55. }

贪心

贪心基本思想

贪心算法是一种在每一步选择中都采取当前状态下最好或最优（即最有利）的选择，从而希望导致结果是最好或最优的算法。其核心思想是在每一步选择中都追求当前最优解，并希望通过这种局部最优的选择来达到全局最优解。

部分背包O(nlogn)

思想：

时间复杂度：O(nlogn)

P2240 【深基12.例1】部分背包问题 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

  1. #include<bits/stdc++.h>
  2. const int N=1e3+10;
  3. const double eps=1e-6; 
  4. using namespace std;
  5.  
  6. struct node{
  7. 	int v,m;
  8. 	double p;
  9. }a[N];
  10. bool cmp(node a,node b){
  11. 	return a.p>b.p;
  12. }
  13. int main()
  14. {
  15.     int n,t;
  16.     cin>>n>>t;
  17.     for(int i=1;i<=n;i++)
  18.     {
  19.     	cin>>a[i].m>>a[i].v;
  20.     	a[i].p=a[i].v*1.0/a[i].m;
  21. 	}
  22. 	sort(a+1,a+1+n,cmp);
  23. 	
  24. 	double sum=0;//价值，体积 
  25. 	for(int i=1;i<=n;i++)
  26. 	{
  27. 		if(t-a[i].m>eps)
  28. 		{
  29. 			t-=a[i].m;
  30. 			sum+=a[i].v;
  31. 		}else{
  32. 			sum+=t*a[i].p;
  33. 			break;
  34. 		}
  35. 	}
  36. 	printf("%.2f",sum);
  37. 	
  38.     return 0;
  39. }

活动安排问题O(nlogn)

按照活动的结束时间排序，从前往后选即可。

活动安排问题本质就是要求最多有多少个不重复的区间。

贪心算法思想

对于最大不相交区间数量问题，贪心算法的核心思想是每次选择结束时间最早的区间，这样可以留出更多的空间给后面的区间，以便选择更多的区间。

算法步骤

  1. 排序：按区间的结束时间从小到大排序。
  2. 选择区间：从第一个区间开始，依次选择结束时间最早且与前一个选择的区间不重叠的区间。

时间复杂度分析

  1. 排序步骤：将所有区间按结束时间从小到大排序，时间复杂度为 O(nlog⁡n)。
  2. 选择步骤：遍历所有区间，选择不重叠的区间，时间复杂度为 O(n)。

908. 最大不相交区间数量 - AcWing题库

  1. #include<bits/stdc++.h>
  2. const int N=1e3+10;
  3. const double eps=1e-6; 
  4. using namespace std;
  5.  
  6. struct node{
  7. 	int a,b;
  8. }c[N];
  9. bool cmp(node a,node b){
  10. 	return a.b<b.b;
  11. }
  12. int main()
  13. {
  14.     int n;
  15.     cin>>n;
  16.     for(int i=1;i<=n;i++)
  17.     {
  18.     	cin>>c[i].a>>c[i].b;
  19. 	}
  20. 	sort(c+1,c+1+n,cmp);
  21. 	
  22. 	int lst=-1e9,ans=0;
  23. 	for(int i=1;i<=n;i++)
  24. 	{
  25. 		if(c[i].a>lst) 
  26. 		{
  27. 			ans++;
  28. 			lst=c[i].b;
  29. 		}
  30. 	}
  31. 	
  32. 	cout<<ans<<'\n';
  33.     return 0;
  34. }

哈夫曼编码O(nlogn)

哈夫曼编码的思想

  1. 统计频率：计算每个字符在待压缩数据中的出现频率。

  2. 构建优先队列：将每个字符及其频率作为一个叶子节点，创建一个优先队列（通常用最小堆实现），按频率从小到大排序。

  3. 构建哈夫曼树：重复以下步骤，直到队列中只剩一个节点：

    • 从队列中取出两个频率最小的节点，创建一个新节点作为这两个节点的父节点，新节点的频率为两个子节点频率之和。
    • 将新节点插回优先队列中。

  4. 生成编码表：通过遍历哈夫曼树，生成每个字符的哈夫曼编码。通常，左子节点表示0，右子节点表示1。

  5. 编码和解码：用生成的哈夫曼编码表对数据进行编码和解码。

示例

假设有一组字符及其对应的频率：

字符频率
A5
B9
C12
D13
E16
F45

步骤

  1. 统计频率：已知频率。
  2. 构建优先队列：
    • 初始队列：(5, A), (9, B), (12, C), (13, D), (16, E), (45, F)。
  3. 构建哈夫曼树：
    • 取出 (5, A) 和 (9, B)，创建新节点 (14)，插入队列：(12, C), (13, D), (14), (16, E), (45, F)。
    • 取出 (12, C) 和 (13, D)，创建新节点 (25)，插入队列：(14), (16, E), (25), (45, F)。
    • 取出 (14) 和 (16, E)，创建新节点 (30)，插入队列：(25), (30), (45, F)。
    • 取出 (25) 和 (30)，创建新节点 (55)，插入队列：(45, F), (55)。
    • 取出 (45, F) 和 (55)，创建新节点 (100)，插入队列：(100)。
  4. 生成编码表：
    • 通过遍历哈夫曼树生成编码表：
      • F: 0
      • C: 100
      • D: 101
      • A: 1100
      • B: 1101
      • E: 111

148. 合并果子 - AcWing题库

  1. #include<bits/stdc++.h>
  2. const int N=1e5+10;
  3. const double eps=1e-6; 
  4. using namespace std;
  5.  
  6. int a[N];
  7. int main()
  8. {
  9.     int n;
  10.     cin>>n;
  11.     
  12.     priority_queue<int,vector<int>,greater<int>> q;
  13.     for(int i=1;i<=n;i++)
  14.     {
  15.     	cin>>a[i];
  16.     	q.push(a[i]);
  17. 	}
  18. 	
  19. 	int ans=0;
  20. 	while(q.size()!=1)
  21. 	{
  22. 		auto c=q.top();
  23. 		q.pop();
  24. 		auto d=q.top();
  25. 		q.pop();
  26. 		q.push(c+d);
  27. 		ans+=c+d;
  28. 	}
  29. 	cout<<ans<<'\n';
  30.     return 0;
  31. }

最小生成树

Prim算法

Prim算法是用于求解无向连通图的最小生成树（Minimum Spanning Tree, MST）的经典算法。它通过贪心策略逐步扩展生成树，确保每一步都选择权值最小的边，从而保证最终生成的树是最小生成树。

算法思想

  1. 初始化：从图中选择一个任意节点作为起点，将其加入生成树。
  2. 扩展生成树：在不构成环的前提下，从生成树中的节点出发，选择权值最小的边，将这条边连接的另一端节点加入生成树。
  3. 重复步骤2，直到所有节点都被包括在生成树中。

算法步骤

  1. 选择起点：从图中选择一个任意节点（通常选择第一个节点）作为起点，初始化一个空的生成树。
  2. 构建优先队列：使用一个优先队列（最小堆）来存储候选边，初始时将起点的所有边加入优先队列。
  3. 选择最小边：从优先队列中取出权值最小的边，如果这条边连接的节点不在生成树中，则将该节点和边加入生成树。
  4. 更新优先队列：将新加入节点的所有边（未被包括在生成树中的边）加入优先队列。
  5. 重复步骤3和4，直到生成树包含图中的所有节点。

时间复杂度

Prim算法的时间复杂度取决于具体的实现方式：

  • 使用简单数组实现的优先队列，时间复杂度为 O(V^2)。
  • 使用二叉堆（或其他高效堆结构）实现的优先队列，时间复杂度为 O(ElogV)。

其中，V 是图中节点的数量，E 是图中边的数量。

858. Prim算法求最小生成树 - AcWing题库

Kruskal

Kruskal算法是另一种用于求解无向连通图的最小生成树（Minimum Spanning Tree, MST）的经典算法。它通过贪心策略选择图中权值最小的边，并确保不会形成环，从而保证最终生成的树是最小生成树。

算法思想

  1. 初始化：将图中的所有边按权值从小到大排序。
  2. 构建最小生成树：依次从排序后的边中选择权值最小的边，如果这条边连接的两个节点属于不同的连通分量，则将这条边加入生成树，并合并这两个连通分量。
  3. 重复步骤2，直到生成树包含 V−1V-1V−1 条边（其中 VVV 是图中节点的数量）。

数据结构

为了有效地判断两个节点是否属于同一个连通分量以及合并两个连通分量，Kruskal算法使用并查集（Disjoint Set Union, DSU）数据结构。

并查集（DSU）操作

  1. 查找（Find）：找到一个节点所属的连通分量（即找到该节点的代表元）。
  2. 合并（Union）：将两个节点所在的连通分量合并成一个连通分量。

并查集通常通过路径压缩（Path Compression）和按秩合并（Union by Rank）进行优化，以实现接近常数时间的操作。

算法步骤

  1. 初始化：创建一个并查集，将所有节点初始化为独立的连通分量。
  2. 边排序：将所有边按权值从小到大排序。
  3. 构建最小生成树：
    • 遍历排序后的边，对于每条边，检查其连接的两个节点是否属于不同的连通分量。
    • 如果两个节点属于不同的连通分量，则将这条边加入生成树，并合并这两个连通分量。
  4. 终止条件：当生成树包含 V−1V-1V−1 条边时，停止算法。

时间复杂度

  • 边排序：O(Elog⁡E)O(E \log E)O(ElogE)，其中 EEE 是图中的边数。
  • 并查集操作：在路径压缩和按秩合并优化下，单次操作的时间复杂度为 O(α(V))O(\alpha(V))O(α(V))，其中 α\alphaα 是阿克曼函数的反函数，接近常数时间。

总体时间复杂度为 O(Elog⁡E)O(E \log E)O(ElogE)，因为排序是最耗时的步骤。

859. Kruskal算法求最小生成树 - AcWing题库

回溯

回溯的基本思想

回溯法从根节点出发，以深度优先方式搜索整个解空间。这个开始结点成为活结点，同时成为当前的扩展结点。在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个结点就成为新的活结点

01背包O(2^n)

回溯算法通过构建一个决策树来解决问题，每个物品都有两种选择：要么放入背包，要么不放入背包。因此，对于 n 个物品，决策树的叶子节点总数为 2^n。在最坏的情况下，算法需要遍历所有这些节点，以找到最优解或所有可行解，从而导致时间复杂度为 O(2^n)。

  1. #include<bits/stdc++.h>
  2. const int N=1e3+10;
  3. using namespace std;
  4. int v[N],w[N];
  5. int n,val;
  6. int maxn=-1e9;
  7. void dfs(int x,int sumv,int sumw)
  8. {
  9.     if(sumv>val) return ;
  10.     
  11.     if(x>n)
  12.     {
  13.         maxn=max(maxn,sumw);
  14.         return ;
  15.     }
  16.     //选
  17.     dfs(x+1,sumv+v[x],sumw+w[x]);
  18.     //不选
  19.     dfs(x+1,sumv,sumw);
  20. }
  21. int main()
  22. {
  23. 	cin>>n>>val;
  24. 	for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
  25. 	
  26. 	dfs(0,0,0);
  27. 	
  28. 	cout<<maxn<<'\n';
  29.     return 0;
  30. }

问答题

1.动态规划的思想 

对于一个能用动态规划解决的问题，一般采用如下思路解决：

  1. 将原问题划分为若干 阶段，每个阶段对应若干个子问题，提取这些子问题的特征（称之为 状态）；
  2. 寻找每一个状态的可能 决策，或者说是各状态间的相互转移方式（用数学的语言描述就是 状态转移方程）。
  3. 按顺序求解每一个阶段的问题。

动态规划算法的基本要素
1 最优子结构
        矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。
        在分析问题的最优子结构性质时，所用的方法具有普遍性：首先假设由问题的最优解导出的子问题的解不是最优的，然后再设法说明在这个假设下可构造出比原问题最优解更好的解，从而导致矛盾。
        利用问题的最优子结构性质，以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。最优子结构是问题能用动态规划算法求解的前提。
注意：同一个问题可以有多种方式刻划它的最优子结构，有些表示方法的求解速度更快（空间占用小，问题的维度低）

2 重叠子问题
        递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。这种性质称为子问题的重叠性质。
动态规划算法，对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果。
通常不同的子问题个数随问题的大小呈多项式增长。因此用动态规划算法只需要多项式时间，从而获得较高的解题效率。


思想：
        动态规划和分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。
        与分治法不同的是，动态规划法中分解得到的子问题不是互相独立的。若用分治法来解这类子问题，分解得到的子问题数目非常多，最后解决原问题需要耗费指数时间。但是这些子问题有很多是相同的，也就是同一个子问题被计算了很多次，不同子问题的数量可能只有多项式量级。
        如果我们保存已经解决的子问题的解，需要解相同子问题时找出已经计算出的解，这样可以减少大量重复计算，最终得到多项式时间算法。
经常用一个表来记录所有已解决的子问题的解。不管该子问题以后是否被利用，只要它被计算过，就将其结果填入表中。这就是动态规划的基本思想。具体的动态规划算法多种多样，但它们具有相同的填表格式。

2.回溯的思想

        回溯法是一种即带有系统性又带有跳跃性的搜索算法。它在问题的解空间树中，按深度优先策略，从根节点出发搜索解空间树。算法搜索至解空间树的任一结点时，先判断该节点是否包含问题的解。如果不包含，则跳过对以该节点为根的子树的搜索，逐层向其它祖先节点回溯。否则，进入该子树，继续按照深度优先策略搜索。回溯法求问题的所有解时，要回溯到根，且根节点的所有子树都已被搜索遍才结束。

        回溯法求问题的一个解时，只要搜索到问题的一个解就可结束。这种以深度优先方式系统搜索问题的算法称为回溯法，它是用于解组合数大的问题。通俗的讲，某些解空间是非常大的，可以认为是一个非常庞大的树，此时完全遍历的时间复杂度是难以忍受的。此时可以在遍历的同时检查一些条件，当遍历某分支的时候，若发现条件不满足，则退回到根节点进入下一个分支的遍历。这就是“回溯”这个词的来源。而根据条件有选择的遍历，叫做剪枝或分枝定界。

3.贪心的基本要素

1.贪心选择性质

  • 在每一步都做出一个局部最优的选择，这个选择不依赖于之前的选择。
  • 这个局部最优选择最终能导向全局最优解。

2.最优子结构性质

  • 一个问题的最优解包含其子问题的最优解。
  • 这意味着通过解决局部子问题的最优解，可以构建出整个问题的最优解。

3.无后效性

  • 一旦某个阶段的决策做出，这个决策不会受到之后阶段的决策影响。
  • 换句话说，当前决策是独立的，未来的决策不会改变过去的决策。

4.分支限界的思想（分支限界法和回溯的区别 

分支限界法基本思想

  • 分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。
  • 在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。
  • 此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。

分支限界法与回溯法的不同

  1. 求解目标
    声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/我家小花儿/article/detail/891030
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。