计算机算法设计与分析第三章动态规划作业题

冷不防 2023-10-03 17:41 4阅读 0赞

#### 计算机算法设计与分析 第三章 动态规划 作业题 ####

*  一、判断题
 *   *  1-1
     *  1-2
     *  1-3
 *  二、单选题
 *   *  2-1
     *  2-2
     *  2-3
 *  编程题
 *   *  7-1 单调递增最长子序列 (20 分)
     *   *  题目描述
         *  参考代码
         *  习题答案
     *  7-2 租用游艇问题 (17 分)
     *   *  题目描述
         *  参考代码
         *  习题答案
     *  3-3 挖地雷 (22 分)
     *   *  题目描述
         *  参考代码
         *  习题答案
     *  3-4 最低通行费 (22 分)
     *   *  题目描述
         *  参考代码
         *  习题答案

## 一、判断题 ##

### 1-1 ###

如果一个问题可以用动态规划算法解决，则总是可以在多项式时间内解决的。  
T F  
(1分)

### 1-2 ###

最优二叉搜索树的根结点一定存放的是搜索概率最高的那个关键字。

T F

### 1-3 ###

用动态规划而非递归的方法去解决问题时，关键是将子问题的计算结果保存起来，使得每个不同的子问题只需要被计算一次。子问题的解可以被保存在数组或哈希散列表中。

T F

## 二、单选题 ##

### 2-1 ###

在动态规划中，我们要推导出一个子问题的解与其他子问题解的递推关系。要将这种关系转换为自底向上的动态规划算法，我们需要以正确的顺序填写子问题解的表格，使得在解任一子问题时，所有它需要的子问题都已经被解决了。在下列关系式中，哪一个是不可能被计算的？

A.A(i,j)=min(A(i−1,j),A(i,j−1),A(i−1,j−1))  
B.A(i,j)=F(A(min\{i,j\}−1,min\{i,j\}−1),A(max\{i,j\}−1,max\{i,j\}−1))  
C.A(i,j)=F(A(i,j−1),A(i−1,j−1),A(i−1,j+1))  
D.A(i,j)=F(A(i−2,j−2),A(i+2,j+2))

> 画个矩阵就知道了，只能由之前推导出出的也就是左右上方的元素推出来；

### 2-2 ###

给定递推方程 f i,j,k =f i,j+1,k + min0≤l≤k \{f i−1,j,l +wj,l \}。要通过循环解此方程，我们**一定不能**用下列哪种方法填表？

A.for k in 0 to n: for i in 0 to n: for j in n to 0  
B.for i in 0 to n: for j in 0 to n: for k in 0 to n  
C.for i in 0 to n: for j in n to 0: for k in n to 0  
D.for i in 0 to n: for j in n to 0: for k in 0 to n

### 2-3 ###

切原木问题：给定一根长度为N米的原木；另有一个分段价格表，给出长度L=1,2,⋯,M对应的价格PL 。要求你找出适当切割原木分段出售所能获得的最大收益RN 。例如，根据下面给出的价格表，若要出售一段8米长的原木，最优解是将其切割为2米和6米的两段，这样可以获得最大收益R8 =P2+P6=5+17=22。而若要出售一段3米长的原木，最优解是根本不要切割，直接售出。

Length L 1 2 3 4 5 6 7 8 9 10  
Price PL 1 5 8 9 10 17 17 20 23 28  
下列哪句陈述是错的？

A.此问题可以用动态规划求解  
B.若N≤M，则有RN =max\{PN ,max1≤i<N \{Ri +RN−i \}\}  
C.若N>M，则有RN =max1≤i<N \{Ri +RN−M \}  
D.算法的时间复杂度是O(N2 )

## 编程题 ##

### 7-1 单调递增最长子序列 (20 分) ###

#### 题目描述 ####

设计一个O(n2)时间的算法，找出由n个数组成的序列的最长单调递增子序列。

**输入格式:**  
输入有两行： 第一行：n，代表要输入的数列的个数 第二行：n个数，数字之间用空格格开

**输出格式:**  
最长单调递增子序列的长度

**输入样例:**  
在这里给出一组输入。例如：

5
    1 3 5 2 9```
    **输出样例:**
    在这里给出相应的输出。例如：
    
    ```cpp
    4

#### 参考代码 ####

#include <iostream>
    #include <vector>
    using namespace std;
    int main()
    {
        
    	int n;
    	int a[n];
    	cin>>n; 
    	for(int i=0;i<n;i++)
    	{
        
    		cin>>a[i];
    	}
    	int maxl=0;
    	int count=0;
    	vector<int> v;
    	for(int i=0;i<n;i++)
    	{
        
    		v.push_back(a[i]);
    		for(int j=i;j<n;j++)
    		{
        
    			if(a[j]>(*v.rbegin()))//注意要加* 
    			{
        
    				v.push_back(a[j]);
    			}
    		}
    		if(v.size()>maxl)
    		{
        
    			maxl=v.size();
    		}
    		vector<int>().swap(v);//清空vector的方法 
    	}
    	cout<<maxl;
    }
    
    //vector<int>().swap(vecnum);

#### 习题答案 ####

#include <iostream>
    using namespace std;
    /*
    设数字序列为nums[i],len[i]为子序列最后一个数字为nums[i]时的单调递增最长子序列 ，则
    len[i] = max {len[j] + 1 | num[i] > num[j]}, 0 <= j < i
    */
    int main() {
        
    	int n;
    	cin >> n;
    	int nums[n];
    	int len[n];
    	
    	for (int i = 0; i < n; i++)
    		cin >> nums[i];
    	
    	len[0] = 1;
    	for (int i = 1; i < n; i++) {
         // 从左至右填表求len[i]
    		len[i] = 1;
    		for (int j = 0; j < i; j++) {
         //子序列前一个数字可能是nums[0..i-1],求最长子序列 
    			if (nums[i] > nums[j] && len[j] + 1 > len[i]) {
        
    				len[i] = len[j] + 1; 
    			}
    		}
    	}
    		
    	//求以nums[0]、nums[1]...nums[n-1]结尾的序列中，最长的序列 
    	int max = 0;
    	for (int i = 0; i < n; i++) {
        
    		if (len[i] > max) 
    			max = len[i];
    	}
    	
    	cout << max << endl;
    }

> 课上方法： len\[i\]:表示以nums\[i\]为结尾的单调递增子序列长度  
> len\[i\]=max\{len\[j\]+1(nums\[j\]<nums\[i\],0<=j<i)\}

### 7-2 租用游艇问题 (17 分) ###

#### 题目描述 ####

题目来源：王晓东，《算法设计与分析》

长江游艇俱乐部在长江上设置了n个游艇出租站1，2，…，n。游客可在这些游艇出租站租用游艇，并在下游的任何一个游艇出租站归还游艇。游艇出租站i到游艇出租站j之间的租金为r(i,j),1<=i<j<=n。试设计一个算法，计算出从游艇出租站1 到游艇出租站n所需的最少租金。

**输入格式:**  
第1 行中有1 个正整数n（n<=200），表示有n个游艇出租站。接下来的第1到第n-1 行，第i行表示第i站到第i+1站,第i+2站, … , 第n站的租金。

**输出格式:**  
输出从游艇出租站1 到游艇出租站n所需的最少租金。

**输入样例:**  
在这里给出一组输入。例如：

> 3  
> 5 15  
> 7

**输出样例:**  
在这里给出相应的输出。例如：

> 12

![该题参考图][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAR0NUVFRUVFQ_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center]

#### 参考代码 ####

#include <iostream>
    using namespace std;
    int Smaller_one(int a,int b)//两数取较小的一个 
    {
        
    	if(a>b){
        
    		return b;
    	}
    	return a;
    }
    //1<=i<j<=n
    int main()
    {
        
    	int n;
    	cin>>n;
    	// 记录i到j所需要的租金，一个倒三角 
    	int r[n+1][n+1];//下标从1开始 
    	for(int i=1;i<=n;i++)
    	{
        
    		for(int j=i+1;j<=n;j++)
    		{
        
    			cin>>r[i][j];
    		}
    	 } 
    	 
    	 //处理（逐步最优）
    	  int min[n+1]={
        0};//记录从第一个站点到第i个站点的最优解（最少花费）
    	  for(int i=2;i<=n;i++)
    	  {
        
    	  	min[i]=r[1][i];
    	  	for(int j=1;j<i;j++)
    	  	{
        
    	  		min[i]=Smaller_one(min[i],min[j]+r[j][i]);
    		  }
    	  }
    	  
    	  cout<<min[n];
    	 
     }

#### 习题答案 ####

#include <iostream>
    using namespace std;
    const int MAXN = 300;
    int cost[MAXN][MAXN]; // 费用数组
    
    //m[i]代表从第i个租船点到终点的最小费用
    //可选方案为第i个租船点直接到后面的某个租船点，
    //然后从该租船点经过若干租船点到终点
    //可选方案中最小的即为该子问题的解
    // m[i] = max {cost[i][j] + m[j]}, i+1 <= j <= n
    int m[MAXN];
    
    int main() {
        
      int n;
      cin >> n;
      int i, j;
      for (i = 1; i <= n; i++) {
        
          for (j = i + 1; j <= n; j++) {
        
            cin >> cost[i][j];
          }
      }
    
      //动态规划从右至左填表
      m[n] = 0;
      for (i = n - 1; i > 0; i--) {
        
        m[i] = cost[i][i + 1] + m[i + 1];
        for (j = i + 2; j <= n; j++) {
        
            if (cost[i][j] + m[j] < m[i])
                m[i] = cost[i][j] + m[j];
        }
      }
    
      cout << m[1] << endl;
      return 0;
    }

> 课上思路： m\[i\]:表示第i个租船点到终点的最小费用  
> m\[i\]=min\{ cost\[i\]\[j\]+m\[j\]|i<j<=n\}

### 3-3 挖地雷 (22 分) ###

#### 题目描述 ####

在一个地图上有n个地窖（n≤200）,每个地窖中埋有一定数量的地雷。同时，给出地窖之间的连接路径，并规定路径都是单向的,且保证都是小序号地窖指向大序号地窖，也不存在可以从一个地窖出发经过若干地窖后又回到原来地窖的路径。某人可以从任意一处开始挖地雷，然后沿着指出的连接往下挖（仅能选择一条路径），当无连接时挖地雷工作结束。设计一个挖地雷的方案，使他能挖到最多的地雷。

**输入格式:**  
第一行：地窖的个数；

第二行：为依次每个地窖地雷的个数；

下面若干行：

xi yi //表示从xi可到yi，xi<yi。

最后一行为"0 0"表示结束。

**输出格式:**  
k1-k2−…−kv //挖地雷的顺序 挖到最多的雷。

**输入样例:**

> 6  
> 5 10 20 5 4 5  
> 1 2  
> 1 4  
> 2 4  
> 3 4  
> 4 5  
> 4 6  
> 5 6  
> 0 0

**输出样例:**

> 3-4-5-6  
> 34

> （1）用二维数组a\[i\]\[j\]来记录，地雷i到地雷j的路是否为通路  
> 对于a\[i\]\[j\]来说，挖到第j个地雷的最大数是  
> 挖到第i个地雷的最大数加上第j个地窖里地雷的数量  
> s = sum\[i\]+num\[j\]  
> （sum\[i\]的初始值会随着计算挖到这个点的最大值而改变，num只是记录当前地窖地雷数的初始值）  
> （2）path\[i\]的记录方式是，i地雷的最大路径的上一个地窖是j，path\[i\]=j，然后j是从上一个k，path\[j\]=k，以此类推  
> ![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAR0NUVFRUVFQ_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 1]  
> ·从1-2的地雷数是 5+10，途经两个点  
> ·从小路径开啥挖，挖到第i个地雷的最大数量记录在sum\[i\]  
> sum\[2\]=5+10  
> ·要确定从哪个地雷开始挖起  
> ![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAR0NUVFRUVFQ_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 2]

#### 参考代码 ####

//设nums[i]为第i个地窖埋的地雷数
    //count[i]为选择第i个地窖挖时的最大地雷数，则
    //count[i] = max{nums[i] + count[j] | 地窖i、j相连} i<j<=n
    //path[i]记录挖完第i个地窖后，下一个菜窖选择哪一个挖的地雷数最多。
    
    #include <iostream>
    using namespace std;
    
    const int MAX = 210;
    int conn[MAX][MAX] = {
        0}; //记录两个菜窖是否联通
    int count[MAX] = {
        0}; //挖到第i个地窖时的最大地雷数
    int path[MAX] = {
        0}; //记录挖地雷的最优路径
    int main() {
        
    	int n;
    	cin >> n;
    	int nums[n];
    	for (int i = 1; i <= n; i++)
    		cin >> nums[i];
    	while (true) {
        
    		int a, b;
    		cin >> a >> b;
    		if (a == 0 && b == 0) break;
    		conn[a][b] = 1;
    }
    
    //从右至左依次填表
    	for (int i = n; i >= 1; i--) {
        
    		count[i] = nums[i];
    	for (int j = i + 1; j <= n; j++) {
        
    		if (conn[i][j] == 1) {
        
    		int tmp = nums[i] + count[j];
    		if (tmp > count[i]) {
        
    		count[i] = tmp;
    		path[i] = j;
    		}
    	}
    	}
    	
    	}
    
    //比较从哪个菜窖开始挖地雷数最多
    	int max = 0; //挖到最多的地雷数
    	int id = 1; //从哪个菜窖开始挖
    	for (int i = 1; i <= n; i++) {
        
    		if (count[i] > max) {
        
    		max = count[i];
    		id = i;
    	}
    	}
    
    //输出挖地雷路径
    	cout << id;
    	while (path[id] > 0) {
         //path[i]为0时，表示无连接，路径结束
    		cout << "-" << path[id];
    		id = path[id];
    	}
    	
    	cout << endl << max << endl;
    	}

#### 习题答案 ####

#include <iostream>
    using namespace std;
    
    /*
    设nums[i]为第i个地窖埋的地雷数
    count[i]为选择第i个地窖挖时的最大地雷数，则
    count[i] = max{nums[i] + count[j] | 地窖i、j相连} i<j<=n
    path[i]记录挖完第i个地窖后，下一个地窖选择哪一个挖的地雷数最多。 
    */ 
    
    const int MAX = 210; 
    int conn[MAX][MAX] = {
        0}; //记录两个地窖是否联通 
    int count[MAX] = {
        0}; //挖到第i个地窖时的最大地雷数 
    int path[MAX] = {
        0}; //记录挖地雷的最优路径 
    int main() {
        
    	int n;
    	cin >> n;
    	int nums[n];
    	for (int i = 1; i <= n; i++)
    		cin >> nums[i];
    	while (true) {
        
    		int a, b;
    		cin >> a >> b;
    		if (a == 0 && b == 0) break;
    		conn[a][b] = 1;
    	}
    	
    	//从右至左依次填表 
    	for (int i = n-1; i >= 1; i--) {
        
    		count[i] = nums[i];
    		for (int j = i + 1; j <= n; j++) {
        
    			if (conn[i][j] == 1) {
        
    				int tmp = nums[i] + count[j];
    				if (tmp > count[i]) {
        
    					count[i] = tmp;
    					path[i] = j;
    				}
    			}
    		}
    	
    	}
    	
    	//比较从哪个地窖开始挖地雷数最多 
    	int max = 0; //挖到最多的地雷数 
    	int id = 1; //从哪个地窖开始挖 
    	for (int i = 1; i <= n; i++) {
        
    		if (count[i] > max) {
        
    			max = count[i];
    			id = i;
    		}		
    	}
    	
    	//输出挖地雷路径 
    	cout << id;
    	while (path[id] > 0) {
         //path[i]为0时，表示无连接，路径结束 
    		cout << "-" << path[id];
    		id = path[id];
    	}
    	
    	cout << endl << max << endl;
    }

### 3-4 最低通行费 (22 分) ###

#### 题目描述 ####

一个商人穿过一个N×N的正方形的网格，去参加一个非常重要的商务活动。他要从网格的左上角进，右下角出。每穿越中间1个小方格，都要花费1个单位时间。商人必须在(2N-1)个单位时间穿越出去。而在经过中间的每个小方格时，都需要缴纳一定的费用。

这个商人期望在规定时间内用最少费用穿越出去。请问至少需要多少费用？

注意：不能对角穿越各个小方格（即，只能向上下左右四个方向移动且不能离开网格）。

**输入格式:**  
第一行是一个整数，表示正方形的宽度N (1≤N<100)；

后面N行，每行N个不大于100的整数，为网格上每个小方格的费用。

**输出格式:**  
至少需要的费用。

**输入样例:**

> 5  
> 1 4 6 8 10  
> 2 5 7 15 17  
> 6 8 9 18 20  
> 10 11 12 19 21  
> 20 23 25 29 33

**输出样例:**

> 109

样例中，最小值为109=1+2+5+7+9+12+19+21+33。

#### 参考代码 ####

#include <iostream>
    using namespace std;
    int maxn=101;
    int main()
    {
        
    	int n;
    	cin>>n;
    	int a[n+1][n+1];
    	for(int i=0;i<n;i++)
    	{
        
    		for(int j=0;j<n;j++)
    		{
        
    			cin>>a[i][j];
    		}
    	}
    	for(int i=0;i<n;i++)
    	{
        
    		a[i][n]=maxn;
    	}
    	for(int i=0;i<n+1;i++)
    	{
        
    		a[n][i]=maxn;
    	}
    //	for(int i=0;i<n+1;i++)
    //	{
        
    //		for(int j=0;j<n+1;j++)
    //		{
        
    //			cout<<a[i][j]<<" ";
    //		}
    //		cout<<endl;
    //	}
    	int sum=0;
    	int i=0,j=0;
    //	bool flag
    	sum+=a[0][0];
    	while(!(i==n-1&&j==n-1))
    	{
        
    //		if(i==0&&j==0)
    //		{
        
    //			sum+=a[i][j];

#### 习题答案 ####

#include <iostream>
    using namespace std;
    
    /*
    设map[i][j]代表方格[i,j]的费用，
    cost[i][j]代表从方格[i,j]出发到达终点的费用，则
    cost[i][j] = map[i][j] + max {cost[i+1][j], cost[i][j+1] } 
    */ 
    
    const int MAX = 110;
    int map[MAX][MAX] = {
        0};
    int cost[MAX][MAX] = {
        0};
    int main() {
        
    	int n;
    	cin >> n;
    	for (int i = 1; i <= n; i++) {
        
    		for (int j = 1; j <= n; j++) {
        
    			cin >> map[i][j];
    		}
    	} 
    	
    	cost[n][n] = map[n][n];
    	//初始化第n行的最少费用
    	for (int i = n-1; i >= 1; i--) 
    		cost[n][i] = map[n][i] + cost[n][i+1];
    	//初始化第n列的最少费用	
    	for (int i = n-1; i >= 1; i--) 
    		cost[i][n] = map[i][n] + cost[i+1][n];
    	
    	//从下向上，从右向左填表 
    	for (int i = n-1; i >= 1; i--) {
        
    		for (int j = n-1; j >= 1; j--) {
        
    			if (cost[i+1][j] < cost[i][j+1])
    				cost[i][j] = map[i][j] + cost[i+1][j];
    			else
    				cost[i][j] = map[i][j] + cost[i][j+1];
    		}
    	}
    	
    	cout << cost[1][1] << endl;
    	return 0;
    }

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAR0NUVFRUVFQ_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center]: https://img-blog.csdnimg.cn/53fc933537ec4118bed8bb8ad3365955.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAR0NUVFRUVFQ=,size_20,color_FFFFFF,t_70,g_se,x_16#pic_center
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAR0NUVFRUVFQ_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 1]: https://img-blog.csdnimg.cn/7dfd631daec1409da8445f72623c2c6b.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAR0NUVFRUVFQ=,size_20,color_FFFFFF,t_70,g_se,x_16#pic_center
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAR0NUVFRUVFQ_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 2]: https://img-blog.csdnimg.cn/aed7da1f94244cccad324059ce3139d0.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAR0NUVFRUVFQ=,size_20,color_FFFFFF,t_70,g_se,x_16#pic_center