算法设计与分析Lab02

问题描述

设有一个长度为$L$的钢条，在钢条上标有$n$个位置点$(p_1,p_2,\dots,p_n)$。现在需要按钢条上标注的位置将钢条切割为$n+1$段，假定每次切割所需要的代价与所切割的钢条长度成正比。请编写一个算法，能够确定一个切割方案，使切割的总代价最小。

#include <iostream>
#include <string>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;

// 算法要求：请编写一个算法，能够确定一个切割方案，使切割的总代价最小。
// 函数原型： 
void MinCost(int L,int n,int *p){
	
}
//你的代码只需要补全上方函数来实现算法,可根据自己需要建立别的函数
//其中L是钢条长度，n是位置点个数，p包含n 个切割点的位置（乱序）
//只需要提交这几行代码，其他的都是后台系统自动完成的。类似于 LeetCode

int main() {
	// 后台自动给出测试代码放在这里，无需同学编写
	int L, n;
	cin>>L>>n;
	int *p;
	p = new int[n+2];
	p[0] = 0;
	p[n+1] = L;
	for(int i=1;i<n+1;i++){
		cin>>p[i];
	}
	//调用函数输出一个切割最小的代价和，结果通过cout输出，均为int类型
	MinCost(L,n,p);
	return 0;
}

样例输入：

7 4
1 3 4 5

样例输出：

16

问题分析

1. 定义子问题：
   考虑在切割点 $p[i]$ 和 $p[j]$ 之间的最小切割成本。我们可以将这个问题拆分为更小的子问题，即在 $p[i]$ 和 $p[j]$ 之间进行切割。

2. 切割点的选择：
   在 $p[i]$ 和 $p[j]$ 之间的切割点 $k$ 可以是任何 $p[k]$，其中 $i < k < j$。根据选择的切割点，我们可以把区间分成两部分：

   1. 左半部分：从 $p[i]$ 到 $p[k]$，其最小切割成本为 $dp[i][k]$。
   2. 右半部分：从 $p[k]$ 到 $p[j]$，其最小切割成本为 $dp[k][j]$。

   此时，整个区间的成本包括切割点 $k$ 的成本，即 $p[j] - p[i]$。

3. 状态转移方程：
   因此，最小成本的递归关系可以表示为：

$$dp[i][j] = \min_{i < k < j} \left( dp[i][k] + dp[k][j] + (p[j] - p[i]) \right)$$

于是这个问题可以不断分解，直到子问题的规模足够小（例如，当 $i + 1 = j$ 时），此时没有需要切割的区间，成本为 0。因此这个问题具有 最优子结构 的性质，可以使用动态规划法求解。

算法设计

算法步骤

1. 初始化与排序：
   首先，将切割点数组 $p$ 中的切割点按位置顺序重排，并在头尾增加 0 和 $L$，以便更好地表示切割区间。

2. 建立动态规划表：
   创建一个二维数组 $dp[i][j]$，并将其元素全部初始化为0，其中 $dp[i][j]$ 表示在切割点 $p[i]$ 和 $p[j]$ 之间的最小切割成本。

3. 填充动态规划表：
   a) 从小到大遍历切割段的长度。对于从 $i$ 到 $j$ 的这段，尝试所有可能的切割点 $k$（$i<k<j$）。
   b) 对于每一个可能的切割点 $k$，计算切割成本，并选择最小的值更新 $dp[i][j]$。

4. 返回最终结果：
   $dp[0][n + 1]$ 就是整条钢条的最小切割成本。

复杂度分析

时间复杂度分析

1. 对$n$个分割点重排，最多$O(n^2)$。
2. 建立dp数组的时间复杂度为 $O(n^3)$。
   a) 外层循环遍历所有长度 $len$，为 $O(n)$。
   b) 内层两个循环遍历所有的切割点左端点 $i$，也为 $O(n)$。
   c) 对于每一对 $i,j$，内层循环遍历所有可能的切割点 $k$，最多 $O(n)$。

于是，总体的时间复杂度为 $O(n^3)$

空间复杂度分析

上述算法使用了一个大小为 $O(n^2)$ 的动态规划表 $dp$，所以空间复杂度为 $O(n^2)$。

算法实现

定义类

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

void MinCost(int L, int n, int *p) {
	// 对切割点进行排序
	sort(p + 1, p + n + 1);
	
	// 增加头尾点
	p[0] = 0;
	p[n + 1] = L;
	
	// 动态规划数组
	vector<vector<int>> dp(n + 2, vector<int>(n + 2, 0));
	
	// 计算每段的最小切割成本
	for (int len = 2; len <= n + 1; len++) {
		for (int i = 0; i + len <= n + 1; i++) {
			int j = i + len;
			dp[i][j] = INT_MAX;
			for (int k = i + 1; k < j; k++)
			dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + p[j] - p[i]);
		}
	}
	
	// 输出最小切割成本
	cout << dp[0][n + 1] << endl;
}

主函数

int main() {
	int L = 7, n = 4;
	int *p = new int[n + 2];
	p[0] = 1;
	p[1] = 3;
	p[2] = 4;
	p[3] = 5;
	MinCost(L, n, p); // 调用函数输出一个切割最小的代价
	
	delete[] p; // 释放动态分配的内存
	return 0;
}

运行结果