项目GitHub地址：Algorithms_experiments
实验一：递归与分治
实验目的
理解递归算法的思想和递归程序的执行过程，并能熟练编写递归程序。
掌握分治算法的思想，对给定的问题能设计出分治算法予以解决。
实验预习内容
编程实现讲过的例题：二分搜索、合并排序、快速排序。
对本实验中的问题，设计出算法并编程实现。
实验内容和步骤
快速排序及第k小数
快速排序
问题分析及算法思路
快速排序的基本思想：
- 通过一趟排序将待排序列分割成独立的两部分，其中一部分的值比另一部分的小，则分别对两部分序列继续进行排序，达到整个序列有序
实现逻辑：
使用分治法将序列分成两个子序列
- 从序列中选出一个元素，称为基准值（pivot），即确定分界点，可以选取$q[1]$,$q[(1+r)/2]$,$q[r]$或者随机
- 重新排序序列，所有元素小于基准值的放在基准值前面，所有元素比基准值大的摆在基准的后面（相同的数规定放到确定的某一边）。分区推出之后，基准处于中间位置，这一步称为调整区间
- 对于分出的两个子序列继续进行上述操作，递归处理左右两段
对于调整区间可实现的方法有：
- 开辟额外的数组a[]、b[]
- 扫描$q[1:r]$
- 当$q[i] \le x$时，将x插入到a[]
- 当$q[i] \ge x$时，将x插入到b[]
- 分别将a[],b[]中的数放在q中
双指针法，设置i、j指针分别指向第一个和末尾一个，分别向左向右移动，知道重合
在本实验中，使用双指针法进行快排
算法设计与代码实现
void quicksort(int q[], int l, int r)
{
if (l >= r) return; //判边界
int x = q[l], i = l - 1, j = r + 1;
while (i < j)
{
do i ++ ; while (q[i] < x);
do j -- ; while (q[j] > x);
if (i < j) swap(q[i], q[j]);
}
quicksort(q, l, j), quicksort(q, j + 1, r);
}算法演示
经过多次测试，算法的运行结果均正确，符合题意。
快速排序的算法时间复杂度是$O(N*logN)$
第k小数
这道题目是课外思考题top_k的一个变式，找到序列中第k小的数
问题分析及算法思路
基于快速排序的减治法
借用“快速排序”的思想，对整个序列进行划分(取序列第一个元素作为枢轴，也可采用随机法、三数取中法等方法)，并返回划分后的位置，若等于k则得到答案；若大于k，则说明该元素左边的元素都小于k，递归求解该位置前面序列第k小的元素即可；若小于k，则递归求解该位置后面序列第k - count(count为该序列中[l,j]的元素数量，其中j为划分后的元素位置)小的元素即可。由此，每次仅需求解大问题的一个子问题，最后即可得到第k小的数。
冒泡排序
使用冒泡排序的思想，每次冒泡都是找到了序列中的第i小的数（i为冒泡次数），i=k时找到第k小数
堆排序
堆排序中，每次弹出一个最小的值，只需要执行k次弹数操作就可以得到第k小数
堆
是一个完全二叉树
每个节点的值都大于或等于其叶子的值，为最大堆；反之为最小堆
堆排序
- 将待排序的序列构造成一个最大堆，此时序列的最大值为根节点
- 依次将根节点与待排序序列的最后一个元素交换
- 再维护从根节点到该元素的前一个节点为最大堆，如此往复，得到一个递增序列
算法设计与代码实现
减治法
int quicksort(int a[], int l, int r)
{
int pivot = a[l];
int i = l - 1, j = r + 1;
do
{
do { i++; } while (a[i] < pivot);
do { j--; } while (a[j] > pivot);
if (i < j) swap(a[i], a[j]);
} while (i < j);
return j;
}
void Top_k(int a[], int l, int r, int k)
{
if (l >= r) return;
int j = quicksort(a, l, r);
int count = j - l + 1;
if (count == k)
{
return;
}
else if(count > k)
{
Top_k(a, l, j, k);
}
else
{
Top_k(a, j + 1, r, k - count);
}
}
冒泡排序
void bubblesort(int a[], int k, int n)
{
for (int i = 0; i < k; i++)
{
for (int j = n - 2; j >= i; j--)
{
if (a[j + 1] < a[j])
{
int temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}
}
}
}
堆排序
void down(int u)
{
int t = u; // t为点、左孩子、右孩子三个点中最小的一个点
if (u * 2 <= cnt && h[u * 2] < h[t]) t = u * 2;
if (u * 2 + 1 <= cnt && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
if (u != t) // 根节点不是最小的
{
// 与最小的点交换
swap(h[u], h[t]);
down(t); // 递归处理
}
}
void up(int u)
{
while (u / 2 && h[u] < h[u / 2])
{
swap(h[u / 2], h[u]);
u >>= 1; // u /= 2换上去
}
}
void HeapSort(int h[], int k, int n)
{
for (int i = n / 2; i; i--) down(i); // O(n)的时间复杂度建堆
while (m--)
{
if(m == 0){
cout<<h[1]<<endl;
}
h[1] = h[cnt--];
down(1);
}
}
经过测试，上述方法均能实现查找第k小数的功能
关于上述方法的时间复杂度分析
- 对于减治法，时间复杂度是$O(n)$
- 对于冒泡排序，时间复杂度是$O(kn)$
- 对于堆排序，由于需要构建完整堆，时间复杂度是$O(n*logn)$
对于减治法，设每次划分的pivot恰好是序列的中值，可以保证每一次减治去掉一半的区间，由于一次划分耗费$O(n)$的时间，因此只需要处理剩下的一半大小的子序列，得到递推公式
$$
T(n)=T(n/2)+O(n)\
T(n)=O(n)
$$
棋盘覆盖问题
问题描述
在一个$2^k*2^k$方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖；
问题分析与算法思路
采用分治的思想，首先将棋盘进行划分：
- 当k=0时，是一个**$1*1$的棋盘**，棋盘中的骨牌数是0
- 当k>0时，将$2^k*2^k$分割成4个$2^{k-1}*2^{k-1}$的子棋盘，特殊方格必定位于4个子棋盘注意，其余3个子棋盘中没有特殊方格
对于划分出来的四个子棋盘，用一个L型骨牌覆盖3个没有特殊方格的子棋盘的连接处
至此，对每个棋盘按照左上、右上、右下、左下的顺时针顺序铺满棋盘；每次都对分割后的四个小方块进行特殊方格判断：
- 如果特殊方块在里面，递归
- 不在，根据分割的不同位置，把三个角落的方格标记为特殊方块，递归、
算法设计与代码实现
// 函数：棋盘覆盖
void chessboardCover(int tr, int tc, int dr, int dc, int size) {
if (size == 1)
return;
int t = tileID++;
int s = size / 2;
// 左上角子棋盘
if (dr < tr + s && dc < tc + s)
chessboardCover(tr, tc, dr, dc, s);
else {
// 不在左上角，用t号骨牌覆盖右下角
board[tr + s - 1][tc + s - 1] = t;
// 覆盖其他方格
chessboardCover(tr, tc, tr + s - 1, tc + s - 1, s);
}
// 右上角子棋盘
if (dr < tr + s && dc >= tc + s)
chessboardCover(tr, tc + s, dr, dc, s);
else {
// 不在右上角，用t号骨牌覆盖左下角
board[tr + s - 1][tc + s] = t;
// 覆盖其他方格
chessboardCover(tr, tc + s, tr + s - 1, tc + s, s);
}
// 左下角子棋盘
if (dr >= tr + s && dc < tc + s)
chessboardCover(tr + s, tc, dr, dc, s);
else {
// 不在左下角，用t号骨牌覆盖右上角
board[tr + s][tc + s - 1] = t;
// 覆盖其他方格
chessboardCover(tr + s, tc, tr + s, tc + s - 1, s);
}
// 右下角子棋盘
if (dr >= tr + s && dc >= tc + s)
chessboardCover(tr + s, tc + s, dr, dc, s);
else {
// 不在右下角，用t号骨牌覆盖左上角
board[tr + s][tc + s] = t;
// 覆盖其他方格
chessboardCover(tr + s, tc + s, tr + s, tc + s, s);
}
}算法演示
经过多组测试，算法运行正确
算法分析
分析时间复杂度：
递推式
$$
T(k)=\left{\begin{array}{cc}
O(1) & k=0 \
4 T(k-1)+O(1) & k>0
\end{array}\right.
$$
解得
$$
T(k)=O(4^k)
$$
设$n=2^k$，得到时间复杂度是$O(n^2)$
实验总结
分治即“分而治之”，一个规模很大的问题若要直接求解起来是非常困难的，将一个复杂的问题分解为若干个规模较小但是类似于原问题的子问题，子问题可以再分为更小的子问题，最终达到子问题可以简单的直接求解的目的，那么原问题的解即子问题的解的并集。分治算法可以缩小问题的规模，使得问题的求解变得十分容易。
附录
快速排序源代码
#include<iostream>
#include<algorithm>
#define N 20
using namespace std;
void quicksort(int q[], int l, int r)
{
if (l >= r) return; //判边界
int x = q[l], i = l - 1, j = r + 1;
while (i < j)
{
do i ++ ; while (q[i] < x);
do j -- ; while (q[j] > x);
if (i < j) swap(q[i], q[j]);
}
quicksort(q, l, j), quicksort(q, j + 1, r);
}
int main(){
int n,q[N];
cout<<"请输入元素个数与序列："<<endl;
cin>>n;
for(int i=0;i<n;i++){
cin>>q[i];
}
quicksort(q,0,n-1);
for(int i=0;i<n;i++){
cout<<q[i]<<" ";
}
cout<<endl;
system("pause");
return 0;
}
第k小数源代码
减治法
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 20;
int quicksort(int a[], int l, int r)
{
int pivot = a[l];
int i = l - 1, j = r + 1;
do
{
do { i++; } while (a[i] < pivot);
do { j--; } while (a[j] > pivot);
if (i < j) swap(a[i], a[j]);
} while (i < j);
return j;
}
void Top_k(int a[], int l, int r, int k)
{
if (l >= r) return;
int j = quicksort(a, l, r);
int count = j - l + 1;
if (count == k)
{
return;
}
else if(count > k)
{
Top_k(a, l, j, k);
}
else
{
Top_k(a, j + 1, r, k - count);
}
}
int main()
{
int a[N], k, n;
cout << "请输入元素个数与序列:" << endl;
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> a[i];
}
cout << "请输入要获得的第k小数" << endl;
cin >> k;
Top_k(a, 0, n - 1, k);
cout << "第" << k << "小数是" << a[k - 1] << endl;
cout << endl;
return 0;
}冒泡排序
#include<iostream>
using namespace std;
const int N = 20;
void bubblesort(int a[], int k, int n)
{
for (int i = 0; i < k; i++)
{
for (int j = n - 2; j >= i; j--)
{
if (a[j + 1] < a[j])
{
int temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}
}
}
}
int main()
{
int a[N], k, n;
cout << "请输入元素个数与序列:" << endl;
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> a[i];
}
cout << "请输入要获得的第k小数" << endl;
cin >> k;
bubblesort(a, k, n);
cout << a[k - 1] << endl;
return 0;
}堆排序
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100010;
int n, m;
int h[N], cnt;
void down(int u)
{
int t = u; // t为点、左孩子、右孩子三个点中最小的一个点
if (u * 2 <= cnt && h[u * 2] < h[t]) t = u * 2;
if (u * 2 + 1 <= cnt && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
if (u != t) // 根节点不是最小的
{
// 与最小的点交换
swap(h[u], h[t]);
down(t); // 递归处理
}
}
void up(int u)
{
while (u / 2 && h[u] < h[u / 2])
{
swap(h[u / 2], h[u]);
u >>= 1; // u /= 2换上去
}
}
void HeapSort(int h[], int k, int n)
{
for (int i = n / 2; i; i--) down(i); // O(n)的时间复杂度建堆
while (m--)
{
if(m == 0){
cout<<h[1]<<endl;
}
h[1] = h[cnt--];
down(1);
}
}
int main()
{
cin>>n>>m;
for (int i = 1; i <= n; i++) cin>>h[i];
cnt = n;
HeapSort(h, m, n);
return 0;
}棋盘覆盖问题源代码
#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
using namespace std;
int num = 1; //L型骨牌的编号(递增)
int board[100][100]; //棋盘
/*****************************************************
* tr--当前棋盘左上角的行号
* tc--当前棋盘左上角的列号
* dr--当前特殊方格所在的行号
* dc--当前特殊方格所在的列号
* size：当前棋盘的:2^k
*****************************************************/
void chessboardCover(int tr, int tc, int dr, int dc, int size) {
if (size == 1)
return;
int t = num++;
int s = size / 2;
// 左上角子棋盘
if (dr < tr + s && dc < tc + s)
chessboardCover(tr, tc, dr, dc, s);
else {
// 不在左上角，用t号骨牌覆盖右下角
board[tr + s - 1][tc + s - 1] = t;
// 覆盖其他方格
chessboardCover(tr, tc, tr + s - 1, tc + s - 1, s);
}
// 右上角子棋盘
if (dr < tr + s && dc >= tc + s)
chessboardCover(tr, tc + s, dr, dc, s);
else {
// 不在右上角，用t号骨牌覆盖左下角
board[tr + s - 1][tc + s] = t;
// 覆盖其他方格
chessboardCover(tr, tc + s, tr + s - 1, tc + s, s);
}
// 左下角子棋盘
if (dr >= tr + s && dc < tc + s)
chessboardCover(tr + s, tc, dr, dc, s);
else {
// 不在左下角，用t号骨牌覆盖右上角
board[tr + s][tc + s - 1] = t;
// 覆盖其他方格
chessboardCover(tr + s, tc, tr + s, tc + s - 1, s);
}
// 右下角子棋盘
if (dr >= tr + s && dc >= tc + s)
chessboardCover(tr + s, tc + s, dr, dc, s);
else {
// 不在右下角，用t号骨牌覆盖左上角
board[tr + s][tc + s] = t;
// 覆盖其他方格
chessboardCover(tr + s, tc + s, tr + s, tc + s, s);
}
}
int main()
{
int size;
cout << "输入棋盘的size(大小必须是2的n次幂): ";
cin >> size;
int index_x, index_y;
cout << "输入特殊方格位置的坐标: ";
getchar();
cin>>index_x>>index_y;
chessboardCover(0, 0, index_x - 1, index_y - 1, size);
for (int i = 0; i < size; i++)
{
for (int j = 0; j < size; j++)
cout << board[i][j] << "\t";
cout << endl;
}
}实验四：动态规划
计算矩阵连乘积
问题描述
在科学计算中经常要计算矩阵的乘积。矩阵A和B可乘的条件是矩阵A的列数等于矩阵B的行数。若A是一个$p×q$的矩阵，B是一个$q×r$的矩阵，则其乘积C=AB是一个$p×r$的矩阵。由该公式知计算C=AB总共需要pqr次的数乘。其标准计算公式为：
$$
C_{ij}=\sum_{k=1}^qA_{ik}B_{kj}(1\le i\le p,1\le j \le r)
$$
现在问题是现在的问题是，给定n个矩阵$\lbrace A1,A2,…,An \rbrace$。其中Ai与Ai+1是可乘的，i=1,2,…,n-1。要求计算出这n个矩阵的连乘积A1A2…An。
问题分析与算法思想
设二维数组$m[N][N]$表示当前矩阵的连乘次数，一维数组$p[N]$表示各矩阵的维度（其中$p[0]$表示第一个矩阵的行数，$p[i]$表示第i个矩阵的列数），则得到以下递推公式：
$$
m[i][j]=\left{\begin{array}{cc}
0 & i=j \
\min {i \leq k<j}\left{m[i][k]+m[k+1][j]+p{i-1} p_k p_j\right} & i<j
\end{array}\right.
$$
将m数组的对角线初始化为0，然后依次计算第i个矩阵与第i+r-1个矩阵到最后一个矩阵连乘的最优解情况：依次在r-1个分隔位置中依次检测最优分隔点：对于每个分隔点，变换依次分隔位置，再进行逐一测试，如果有更有的分隔点，就替换掉当前的分隔点。
由此，输出$m[1][n]$，得到最少的连乘计算次数；记录间隔位置，可以输出计算连乘的顺序，即最佳添加括号的方式
算法设计与代码实现
void MatrixChain(int n)
{
int r, i, j, k;
for (i = 0; i <= n; i++) // 初始化对角线
{
m[i][i] = 0;
}
for (r = 2; r <= n; r++) // r 个矩阵连乘
{
for (i = 1; i <= n - r + 1; i++) // 依次计算每r个矩阵相连乘的最优解情况
{
j = i + r - 1;
m[i][j] = m[i][i] + m[i + 1][j] + p[i - 1] * p[i] * p[j];
s[i][j] = i; // 分隔位置
for (k = i + 1; k < j; k++) // 变换分隔位置，逐一测试
{
int t = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j];
if (t < m[i][j]) // 如果变换后的位置更优，则替换原来的分隔方法
{
m[i][j] = t;
s[i][j] = k;
}
}
}
}
}算法演示：
算法讨论
通过动态规划来确定矩阵连乘顺序的时间复杂度是$O(n^3)$，在大规模矩阵连乘是，选择最优的连乘顺序，可以大幅度减少计算量，提高计算效率
防卫导弹
问题描述
一种新型的防卫导弹可截击多个攻击导弹。它可以向前飞行，也可以用很快的速度向下飞行，可以毫无损伤地截击进攻导弹，但不可以向后或向上飞行。但有一个缺点，尽管它发射时可以达到任意高度，但它只能截击比它上次截击导弹时所处高度低或者高度相同的导弹。现对这种新型防卫导弹进行测试，在每一次测试中，发射一系列的测试导弹（这些导弹发射的间隔时间固定，飞行速度相同），该防卫导弹所能获得的信息包括各进攻导弹的高度，以及它们发射次序。现要求编一程序，求在每次测试中，该防卫导弹最多能截击的进攻导弹数量，一个导弹能被截击应满足下列两个条件之一：
- 它是该次测试中第一个被防卫导弹截击的导弹
- 它是在上一次被截击导弹的发射后发射，且高度不大于上一次被截击导弹的高度的导弹
输入数据：第一行是一个整数n，以后的n各有一个整数表示导弹的高度
输出数据：截击导弹的最大数目
问题分析与算法思想
对于本题的拦截导弹问题，因为一个导弹能被截击应满足高度不大于上一次被截击导弹的高度的导弹可以将其抽象成求一个最长不上升子序列的问题。
以下是最长不上升子序列的一个算法分析：
- 定义状态：我们可以使用一个数组
dp来表示最长不上升子序列的长度。dp[i]表示以第i个元素为结尾的最长不上升子序列的长度。 - 初始化：将
dp数组的所有元素初始化为1，因为每个单独的元素都可以视为一个长度为1的非递增子序列。 - 状态转移：对于每个位置i（从1到n-1），我们需要考虑所有在i之前的位置j（从0到i-1）。如果$nums[i] \le nums[j]$，则可以将元素i添加到以j为结尾的非递增子序列中，从而得到以i为结尾的非递增子序列。因此，我们可以更新$dp[i] = max(dp[i], dp[j] + 1)$。
- 找到最大值：遍历整个dp数组，找到其中的最大值，即为最长不上升子序列的长度。
算法中的一些细节：
- 状态表示$f[i]$：
- 集合：所有以第$i$个数结尾的不升子序列；
- 属性：$Max$
- 状态计算：集合划分——$f[i]$
- 划分依据：最后一个不同的点
- 以上一个数的位置进行划分
- 若$a_i \le a_j$，则$f[i]=max \lbrace f[j]+1 \rbrace(j=0,1,2,···i-1)$
算法设计与代码实现
void FindMissileNum(int n)
{
int res = 0, cnt = 0;
for (int i = 0; i < n; i ++ )
{
f[i] = 1;
for (int j = 0; j < i; j ++ )
if (h[i] <= h[j])
f[i] = max(f[i], f[j] + 1);
res = max(res, f[i]);
}
cout<<res<<endl;
}算法演示：
算法讨论
算法的时间复杂度是$O(n^2)$，可以对遍历进行优化，进行树状数组优化或者二分优化，可以将时间复杂度优化到$O(n logn)$。
皇宫看守
问题描述
太平王世子事件后，陆小凤成了皇上特聘的御前一品侍卫。皇宫以午门为起点，直到后宫嫔妃们的寝宫，呈一棵树的形状；某些宫殿间可以互相望见。大内保卫森严，三步一岗，五步一哨，每个宫殿都要有人全天候看守，在不同的宫殿安排看守所需的费用不同。可是陆小凤手上的经费不足，无论如何也没法在每个宫殿都安置留守侍卫。
请你编程计算帮助陆小凤布置侍卫，在看守全部宫殿的前提下，使得花费的经费最少。
输入数据：数据表示一棵树，描述如下：
第1行 n，表示树中结点的数目。
第2行至第n+1行，每行描述每个宫殿结点信息，依次为：该宫殿结点标号i（0<i<=n），在该宫殿安置侍卫所需的经费k，该边的儿子数m，接下来m个数，分别是这个节点的m个儿子的标号r1，r2，…，rm。
对于一个n（0 < n <= 1500）个结点的树，结点标号在1到n之间，且标号不重复。
输出数据：输出到output.txt文件中。输出文件仅包含一个数，为所求的最少的经费。
如下示例：
sample input
>6 >1 30 3 2 3 4 >2 16 2 5 6 >3 5 0 >4 4 0 >5 11 0 >6 5 0sample output
>25
问题分析与算法思想
这道题目是求权值最小的点支配集，要求图中每个点都能被观察到，因此有下列情况：
- 父节点放置哨兵，所有子节点的哨兵都可放可不放
- 父节点不设置哨兵，至少有一个子节点需要放置哨兵
- 父结点不设置哨兵，但其父节点设置哨兵观察，则子节点哨兵可放可不放
总结上述情况可以得到每个节点总共有三种情况：
- 被父节点看守
- 被子节点看守
- 被节点自身看守
将上述三种情况分别编为0，1，2
建立状态转移函数$f[i][3]$，其中：
- $f[i][0]$表示第i个节点由父节点看守下的最小代价
- $f[i][1]$表示第i个节点由子节点看守下的最小代价
- $f[i][2]$表示第i个节点由自身看守下的最小代价
转移关系：
- $f[i][0] +=min \lbrace f[j][1],f[j][2] \rbrace$
- $f[i][1]=min \lbrace f[i][1],sum-min(f[j][1],f[j][2])+f[j][2] \rbrace$
- $f[i][2]+=min \lbrace min(f[j][0],f[j][1]),f[j][2] \rbrace$
从根节点开始DFS，然后遍历所有当前节点的所有子节点，进行递归。
算法设计与代码实现
void dfs(int u)
{
f[u][2] = w[u];
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i]; // 遍历所有子节点
dfs(j);
f[u][0] += min(f[j][1], f[j][2]);
f[u][2] += min(min(f[j][0], f[j][1]), f[j][2]);
}
f[u][1] = 1e9;
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
// f[u][0]为所有子节点的摆放方案代价之和, 减去 min(f[j][1], f[j][2]) 即是除了j节点其余节点的代价之和
f[u][1] = min(f[u][1], f[j][2] + f[u][0]- min(f[j][1], f[j][2]));
}
}算法演示：
算法讨论
本题是树形DP的应用，涉及到了父节点、子节点的邻接关系。算法遍历了树中的所有节点，时间复杂度是$O(n)$
附录
计算矩阵连乘积源代码
#include<iostream>
using namespace std;
const int N = 100;
int p[N]; // 矩阵规模
int m[N][N]; // 最优解
int s[N][N];
void MatrixChain(int n)
{
int r, i, j, k;
for (i = 0; i <= n; i++) // 初始化对角线
{
m[i][i] = 0;
}
for (r = 2; r <= n; r++) // r 个矩阵连乘
{
for (i = 1; i <= n - r + 1; i++) // 依次计算每r个矩阵相连乘的最优解情况
{
j = i + r - 1;
m[i][j] = m[i][i] + m[i + 1][j] + p[i - 1] * p[i] * p[j];
s[i][j] = i; // 分隔位置
for (k = i + 1; k < j; k++) // 变换分隔位置，逐一测试
{
int t = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j];
if (t < m[i][j]) // 如果变换后的位置更优，则替换原来的分隔方法
{
m[i][j] = t;
s[i][j] = k;
}
}
}
}
}
void print(int i, int j) // 输出连乘顺序
{
if (i == j)
{
cout << "p[" << i << "]";
return;
}
cout << "(";
print(i, s[i][j]);
print(s[i][j] + 1, j);
cout << ")";
}
int main()
{
int n; // n个矩阵
cout << "请输入矩阵的数目：";
cin >> n;
int i, j;
cout << "请输入各个矩阵的维度(相邻维度只需输入一个即可):";
for (i = 0; i <= n; i++)
{
cin >> p[i];
}
MatrixChain(n);
cout << "最佳添加括号的方式为：";
print(1, n);
cout << "\n最小计算量的值为：" << m[1][n] << endl;
return 0;
}
防卫导弹源代码
#include <sstream>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1000;
int h[N], f[N], q[N]; // q数组记录开好的子序列结尾的数
void FindMissileNum(int n)
{
int res = 0;
for (int i = 0; i < n; i ++ )
{
f[i] = 1;
for (int j = 0; j < i; j ++ )
if (h[i] <= h[j])
f[i] = max(f[i], f[j] + 1);
res = max(res, f[i]);
}
cout<<res<<endl;
}
int main()
{
int n=0;
while (cin >> h[n]) n ++ ;
FindMissileNum(n);
return 0;
}皇宫看守源代码
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1510;
int n;
int h[N], w[N], e[N], ne[N], idx;
int f[N][3];
bool st[N];
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
void dfs(int u)
{
f[u][2] = w[u];
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i]; // 遍历所有子节点
dfs(j);
f[u][0] += min(f[j][1], f[j][2]);
f[u][2] += min(min(f[j][0], f[j][1]), f[j][2]);
}
f[u][1] = 1e9;
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
// f[u][0]为所有子节点的摆放方案代价之和, 减去 min(f[j][1], f[j][2]) 即是除了j节点其余节点的代价之和
f[u][1] = min(f[u][1], f[j][2] + f[u][0]- min(f[j][1], f[j][2]));
}
}
int main()
{
cin >> n;
memset(h, -1, sizeof h);
for (int i = 1; i <= n; i ++ )
{
int id, cost, cnt;
cin >> id >> cost >> cnt;
w[id] = cost; // 在点上记录花费
while (cnt -- )
{
int ver;
cin >> ver;
add(id, ver);
st[ver] = true; // 标记不是根节点
}
}
int root = 1;
while (st[root]) root ++ ; // 找到根节点
dfs(root);
cout << min(f[root][1], f[root][2]) << endl;
return 0;
}实验五：贪心算法和随机算法
背包问题
问题描述
有一个背包，背包容量是M=150。有7个物品，物品可以分割成任意大小。要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。
| 物品 | A | B | C | D | E | F | G |
|---|---|---|---|---|---|---|---|
| 重量 | 35 | 30 | 60 | 50 | 40 | 10 | 25 |
| 价值 | 10 | 40 | 30 | 50 | 35 | 40 | 30 |
问题分析及算法思路
首先计算每种物品单位重量的价值，然后依照贪心策略，将尽可能多的单位重量价值最高的物品装入背包。将某种物品全部装入背包，背包内的物品总重量未超过C，则选择单位重量价值次高的物品并尽可能地多装入背包
使用贪心算法解决背包问题的思路如下：
计算每个物品的单位价值：对于每个物品，计算其单位重量的价值（即价值除以重量），并将其降序排序。
初始化结果变量：创建一个结果变量，用于记录当前已选择的物品的总重量和总价值，初始值为0。
遍历物品：按照单位价值降序的顺序，依次遍历每个物品。
判断是否可以放入背包：对于当前遍历到的物品，判断是否可以放入背包中。如果当前物品的重量小于等于背包剩余容量，则将该物品放入背包，并将其重量和价值加到结果变量中。否则，跳过该物品。
返回结果：遍历完所有物品后，返回结果变量中记录的总重量和总价值。
贪心算法的核心思想是每次选择当前最优的解决方案，即单位价值最高的物品放入背包。若某次不按照最大单位重量价值的物品进行放置，所得到的总价值一定不是最大的，则可以确定贪心解就是最优解，保证了贪心策略的正确性。
算法设计与代码实现
struct Obj
{
int id; // 物品序号
int w; // w为各物品的重量
int v; // v为各物品的价值
float unit; // 单位重量的价值
bool operator< (const Obj& W)const
{
return unit < W.unit;
}
}obj[N];
void FindMaxValue(int n, int m)
{
float value = 0;
sort(obj, obj + n); // 按照单位重量的价值对物品进行升序排序
for (int i = n - 1; i >= 0; i--)
{
if (m - obj[i].w >= 0) // 存在剩余容量
{
m -= obj[i].w; // 去掉这部分的背包容量
value += obj[i].v; // 加入这部分的价值
cout << "装入整个第" << l[obj[i].id] << "个物品" << endl;
if (m == 0) break;
}
else
{
float ratio = (float) m / obj[i].w;
cout << "装入" << ratio * 100 << "%第" << l[obj[i].id] << "个物品" << endl;
value += ratio * obj[i].v;
break;
}
}
cout << "装入背包中的物品的总价值最大为" << value << endl;
}算法演示：
算法讨论
背包问题有多个不同的变体，其中一些常见的种类包括：
0/1背包问题（0/1 Knapsack Problem）：在这种问题中，每个物品要么完全放入背包，要么完全不放入背包，不能进行分割。即每个物品只有两种选择：放入背包或不放入背包。
分数背包问题（Fractional Knapsack Problem）：这个问题允许物品被分割放入背包，即可以选择物品的一部分放入背包。每个物品有一个对应的重量和价值，目标是找到使总价值最大化的物品组合。
多重背包问题（Multiple Knapsack Problem）：多重背包问题与0/1背包问题类似，但是每个物品有多个可用的实例（数量不限），可以选择将多个相同的物品放入背包中。
无限背包问题（Unbounded Knapsack Problem）：在这个问题中，每个物品有无限个可用实例，可以无限次地选择物品放入背包。
有限背包问题（Bounded Knapsack Problem）：这个问题介于0/1背包问题和无限背包问题之间，每个物品有一定数量的可用实例，可以选择将物品放入背包的次数受限。
值约束背包问题（Knapsack Problem with Value Constraints）：在这个问题中，除了背包的容量限制外，还有对总价值的限制。目标是找到在满足总重量不超过背包容量的前提下，使总价值最大化的物品组合。
通常来说，背包问题使用动态规划来解决，但是在本题中，物品可以分割成任意大小，故可以通过贪心策略，从最大单位重量价值的物品开始装入背包，是背包的纵价值最大，算法的时间复杂度主要消耗在排序上，使用了C++自带的sort排序，时间复杂度是$O(nlogn)$
照亮的山景
问题描述
在一片山的上空，高度为T处有N个处于不同位置的灯泡，如图。如果山的边界上某一点于某灯i的连线不经过山的其它点，我们称灯i可以照亮该点。开尽量少的灯，使得整个山景都被照亮。山被表示成有m个转折点的折线。
提示：照亮整个山景相当于照亮每一个转折点。
问题分析及算法思路
一座山想要能被照亮，那么把这座山的两侧分别延长，与灯所在的高度相交于两个点，在这个区间内如果有一盏灯，就可以照亮这座山，如果没有，就必须在区间两侧各有一盏灯。那么我们把每座山的区间放到一个集合中，遍历所有的灯，每次贪心的寻找覆盖区间最多的灯，同时将已经照亮的山移出集合，标记灯为已使用，直到集合为空，所求的灯的数量就是最小的灯的数量。
这是在笔算时的解决方案，在计算时应该将其数据化。
首先找到每个顶点能被灯照到的左端点和右端点，可以采用遍历每个灯的做法，计算灯到顶点的直线的斜率 $k$ 和截距 $b$，然后计算该灯到顶点这段距离区间内所有顶点的横坐标投影到该直线的纵坐标是否小于该顶点的纵坐标：
- 若成立，则认为该灯是无法照射到该顶点的，转而判断下一个灯；
- 若这段距离区间中所有顶点都存在以上条件，则认为该灯可以照射到该顶点，由该灯在顶点处的左右关系对顶点能被灯照到的左、右端点进行更新，并判断下一个灯。
若判断的灯已经在该顶点的右侧且该灯无法照到该顶点，则无需继续判断后续灯是否能照射到该顶点。
经过上述过程，我们得到了每个顶点被哪些灯照到, 记录到$l$和$r$中，接着根据贪心策略获得开灯最少的数量：
依次计算区间内每个数出现的次数，找出区间中出现次数最多的数，由贪心策略可知，其是我们要找的灯的序号。点亮该灯后，将能照射到的顶点删除，然后对剩余顶点重复上述过程，直到顶点被全部照亮。
若贪心策略不是最优解，我们可以通过换部分灯的开关情况使其变为最优解，且不增加要亮灯的数目，则该贪心策略是正确的。
算法设计与代码实现
struct Mou
{
int x;
int y;
int l; // l 为顶点能被灯照到的左端点
int r; // r 为顶点能被灯照到的右端点
};
vector<Mou> mou;
void FindLightRegion(int m, int n, int t)
{
for (int i = 0; i < m; i++) // 遍历每个顶点
{
for (int j = 0; j < n; j++) // 遍历每个灯
{
bool flag = true;
if (l[j] != mou[i].x)
{
// 计算直线的斜率k和截距b
float k = (float)(t - mou[i].y) / (l[j] - mou[i].x);
float b = t - k * l[j];
int s = i;
while ((l[j] < mou[i].x && --s && l[j] < mou[s].x)
|| (l[j] > mou[i].x && ++s && l[j] > mou[s].x)) // 遍历灯到该点区间内的所有点
{
if (k * mou[s].x + b < mou[s].y)
{
flag = false;
break;
}
}
}
if (flag)
{
if (mou[i].l == -1)
{
mou[i].l = mou[i].r = j;
}
else
{
mou[i].r++;
}
}
else
{
if (l[j] > mou[i].x)
break; // 无需继续遍历
}
}
}
}
int FindMinLight(int m, int n, int t)
{
int res = 0;
FindLightRegion(m, n, t); // 得到每个顶点被哪些灯照到, 记录到 l 和 r 中
while (mou.size() != 0)
{
// 统计区间每个数出现的次数
int max = 0, cishu = 0;
for (auto t : mou)
{
map<int, int> nums;
for (int i = t.l; i <= t.r; i++)
{
nums[i]++;
}
// 找出区间中出现次数最多的数
for (auto num : nums)
{
if (num.second > cishu)
{
max = num.first;
cishu = num.second;
}
}
}
// 将出现次数最多的数设为当前需要的灯, 然后删除所有有关的顶点
res++;
for (auto it = mou.begin(); it != mou.end();)
{
if (it[0].l <= max && it[0].r >= max)
it = mou.erase(it);
else
++it;
}
}
return res;
}算法演示：
算法讨论
在本题的求解中通过求解每个顶点能被灯照到的左端点和右端点，然后运用贪心策略依次计算区间内每个数出现的次数，找出区间中出现次数最多的数，开相应序号的灯，从而求解开灯最少的数量，算法的时间复杂度是$O(m*n^2)$。
搬桌子问题
问题描述
某教学大楼一层有n个教室，从左到右依次编号为1、2、…、n。现在要把一些课桌从某些教室搬到另外一些教室，每张桌子都是从编号较小的教室搬到编号较大的教室，每一趟，都是从左到右走，搬完一张课桌后，可以继续从当前位置或往右走搬另一张桌子。
输入数据：先输入n、m，然后紧接着m行输入这m张要搬课桌的起始教室和目标教室。
输出数据：最少需要跑几趟。
sample input
10 5 1 3 3 9 4 6 6 10 7 8sample output
3
问题分析及算法实现
使用贪心策略，尽可能在一趟从左向右的移动中移动尽可能多的桌子。
将每一次移动桌子的起始教室和目的教室作为一个区间，对剩余卓子的区间进行比较
- 如果存在剩余桌子的左界限大于上一张桌子的右界限，则可以进行下一张桌子的移动，进行上一步操作
- 反之，则结束这一趟移动，返回下一张桌子的左界限，重复上一个操作
算法设计与代码实现
struct Move {
int start;
int end;
bool use;
bool operator< (const Move& W)const
{
return start < W.start;
}
}mov[N];
int runnum(int n, int m)
{
sort(mov, mov + m); // 按照任务起始教室的编号排序
int res = 0, num = 0, work = 0; // res为趟数
while (work < m)
{
int num = 0; // num为当前到的教室编号
for (int i = 0; i < m; i++)
{
if (mov[i].use == false && mov[i].start >= num)
{
mov[i].use = true;
work++;
num = mov[i].end;
if (num == n) break;
}
}
res++;
}
return res;
}算法演示：
算法讨论
本算法需要进行遍历m张桌子的移动区间，消耗的时间复杂度$O(m^2)$，贪心的策略可以让单趟遍历到的教室属于任务范围内的比例最大，从而使得整个算法性能达到最优。
附录
背包问题源代码
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 20;
char l[35] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
struct Obj
{
int id; // 物品序号
int w; // w为各物品的重量
int v; // v为各物品的价值
float unit; // 单位重量的价值
bool operator< (const Obj& W)const
{
return unit < W.unit;
}
}obj[N];
void FindMaxValue(int n, int m)
{
float value = 0;
sort(obj, obj + n); // 按照单位重量的价值对物品进行升序排序
for (int i = n - 1; i >= 0; i--)
{
if (m - obj[i].w >= 0) // 存在剩余容量
{
m -= obj[i].w; // 去掉这部分的背包容量
value += obj[i].v; // 加入这部分的价值
cout << "装入整个第" << l[obj[i].id] << "个物品" << endl;
if (m == 0) break;
}
else
{
float ratio = (float) m / obj[i].w;
cout << "装入" << ratio * 100 << "%第" << l[obj[i].id] << "个物品" << endl;
value += ratio * obj[i].v;
break;
}
}
cout << "装入背包中的物品的总价值最大为" << value << endl;
}
int main()
{
int n, m; // n为物品数, m为背包容量
cout << "请输入物品数和背包容量:";
cin >> n >> m;
cout << "请输入各个物品的重量和价值:\n";
for (int i = 0; i < n; i++)
{
cin >> obj[i].w >> obj[i].v;
obj[i].id = i;
obj[i].unit = (float) obj[i].v / obj[i].w;
}
FindMaxValue(n, m);
return 0;
}照亮的山景源代码
#include<iostream>
#include<map>
#include<vector>
using namespace std;
const int N = 20;
int l[N], top[N]; // top[N] 表示山峰的编号
struct Mou
{
int x;
int y;
int l; // l 为顶点能被灯照到的左端点
int r; // r 为顶点能被灯照到的右端点
};
vector<Mou> mou;
void FindLightRegion(int m, int n, int t)
{
for (int i = 0; i < m; i++) // 遍历每个顶点
{
for (int j = 0; j < n; j++) // 遍历每个灯
{
bool flag = true;
if (l[j] != mou[i].x)
{
// 计算直线的斜率k和截距b
float k = (float)(t - mou[i].y) / (l[j] - mou[i].x);
float b = t - k * l[j];
int s = i;
while ((l[j] < mou[i].x && --s && l[j] < mou[s].x)
|| (l[j] > mou[i].x && ++s && l[j] > mou[s].x)) // 遍历灯到该点区间内的所有点
{
if (k * mou[s].x + b < mou[s].y)
{
flag = false;
break;
}
}
}
if (flag)
{
if (mou[i].l == -1)
{
mou[i].l = mou[i].r = j;
}
else
{
mou[i].r++;
}
}
else
{
if (l[j] > mou[i].x)
break; // 无需继续遍历
}
}
}
}
int FindMinLight(int m, int n, int t)
{
int res = 0;
FindLightRegion(m, n, t); // 得到每个顶点被哪些灯照到, 记录到 l 和 r 中
while (mou.size() != 0)
{
// 统计区间每个数出现的次数
int max = 0, cishu = 0;
for (auto t : mou)
{
map<int, int> nums;
for (int i = t.l; i <= t.r; i++)
{
nums[i]++;
}
// 找出区间中出现次数最多的数
for (auto num : nums)
{
if (num.second > cishu)
{
max = num.first;
cishu = num.second;
}
}
}
// 将出现次数最多的数设为当前需要的灯, 然后删除所有有关的顶点
res++;
for (auto it = mou.begin(); it != mou.end();)
{
if (it[0].l <= max && it[0].r >= max)
it = mou.erase(it);
else
++it;
}
}
return res;
}
int main()
{
int m, n, t; // m为山棱转折点的个数, n为灯泡个数, t为灯泡的高度
cin >> m;
for (int i = 0; i < m; i++)
{
int x, y;
cin >> x >> y;
mou.push_back({ x,y,-1,-1 }); // 转折点的水平坐标和垂直海拔高度, 并预初始化区间
}
cin >> n >> t;
for (int i = 0; i < n; i++)
{
cin >> l[i];
}
cout << "开灯最少的数量是" << FindMinLight(m, n, t);
return 0;
}搬桌子问题源代码
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 20;
struct Move {
int start;
int end;
bool use;
bool operator< (const Move& W)const
{
return start < W.start;
}
}mov[N];
int runnum(int n, int m)
{
sort(mov, mov + m); // 按照任务起始教室的编号排序
int res = 0, num = 0, work = 0; // res为趟数
while (work < m)
{
int num = 0; // num为当前到的教室编号
for (int i = 0; i < m; i++)
{
if (mov[i].use == false && mov[i].start >= num)
{
mov[i].use = true;
work++;
num = mov[i].end;
if (num == n) break;
}
}
res++;
}
return res;
}
int main()
{
int n, m; // n为教室数, m为要搬运的工作数
cin >> n >> m;
for (int i = 0; i < m; i++)
{
cin >> mov[i].start >> mov[i].end;
mov[i].use = false;
}
cout << runnum(n, m) << endl;
return 0;
}
