高级计算机算法的8道题（贪心、动态规划）
记录这篇的起因：最近要考试了，我又要考试了！！！是之前上过的一门课，然后这次老师划的重点跟没划无差了。毫无头绪，我就开始翻以前上过这门课的资料。（为什么我有点焦虑，是我之前就没学进去）翻着翻着，翻到了我以前的一个算法习题的报告，我就想好久没更新了嘛，直接拿报告传上来，做一个记录好了。里面的内容，以我一贯的做事风格，肯定也是非常认真完成的。（毕竟我真的每次就尽力做好，很少敷衍）如果有错误，也请指正我！所以我就直接传上来，若是里面言辞不太好，也请见谅，三年前肯定也没现在成熟的。
以下就是整个报告的内容
2-1求解最大乘积问题
实验目的：
熟悉贪心算法
实验内容：
问题描述：给定一个无序数组，包含正数，负数和0，要求从中找出3个三个数的乘积，使得乘积最大，并且时间复杂度为O(n)、空间复杂度为O(1)。
输入描述:无序整数数组a[n]。
输出描述:满足条件的最大乘积。
输入示例:
4
3 4 1 2
输出示例:
24
实验结果截图及分析：
该题采用贪心算法，应先对无序数组进行递增排序，由题意可知，在数组中选取三个数，并且这三个数的乘积为最大。对数组排序后，最大乘积即为递增数组中最后三个数的乘积和最大一个数与递增数组中最小两个数的乘积(在前面两个数为负数的情况下)中的最大值。
用代码表示即为MAX{a[n - 1] * a[n - 2] * a[n - 3], a[n - 1] * a[0] * a[1]}
实现核心代码及注释：
// main.cpp
// getMaxMul
// Created by 小可爱 on 2021/11/2.
//
#include <iostream>
#include <algorithm>
using namespace std;
#define MAXSIZE 100
//比较大小
int Max(int num1, int num2) {
if(num1 >= num2) {
return num1;
}else {
return num2;
}
}
int maxMul(int *a, int n) {
//记录最大乘积
int maxMultipleNum;
//排序|递增
sort(a, a + n);
maxMultipleNum = Max(a[n - 1] * a[0] * a[1], a[n - 1] * a[n - 2] * a[n - 3]);
return maxMultipleNum;
}
int main(int argc, const char * argv[]) {
// insert code here...
int a[MAXSIZE], n, maxMultipleNum;
cin >> n;
for(int i = 0; i < n; i++) {
cin >> a[i];
}
maxMultipleNum = maxMul(a, n);
cout << maxMultipleNum << "\n";
return 0;
}2-2求解区间覆盖问题
实验目的：
学会贪心算法
实验内容：
问题描述:用i来表示X坐标轴上坐标为(i-1,i)、长度为1的区间，并给出 n(1 <= n <=200)个不同的整数，表示n个这样的区间。现在要求画m条线段覆盖住所有的区间，条件是每条线段可以任意长，但是要求所画线段的长度之和最小，并且线段的数目不超过 m(1<=m<=50)。
输入描述:输入包括多组数据，每组数据的第1行表示区间个数n和所需线段数m,第2 行表示n个点的坐标。
输出描述:每组输出占一行，输出m条线段的最小长度和。
输入样例:
5 3
1 3 8 5 11
样例输出:
7
实验结果截图及分析
该题同样是采用贪心算法的思路求解。
以下举例讲解我的思路
当所需当线段为1条的时候，我们所需1条线段的最小长度即为11 - 1 + 1，也就是坐标轴上最大的的点的值减去最小的点的值再加1
当所需线段为2条的时候，我们最需要找到相隔最远的两个点的距离，将上面所求得的一条线段断为两段，即可以求得2条线段时，线段的最小长度和。
以此类推，需要3条线段时候需要断开2段，即 m - 1
由此，需要对每相邻两个点的距离进行排序。
最后，需要注意到一个边界值，即当所需线段大于等于点的个数时候，最小长度不变，且为点数n
实现核心代码及注释：
// main.cpp
// sectionCover
// Created by 小可爱 on 2021/11/3.
//
#include <iostream>
using namespace std;
const int MAXSIZE = 50;
//排序｜递增
void sortArray(int *array, int size) {
int min, temp;
for(int i = 0; i < size - 1; i++) {
min = i;
for(int j = i + 1; j < size; j++) {
if(array[min] > array[j]) {
min = j;
}
}
temp = array[i];
array[i] = array[min];
array[min] = temp;
}
}
//求最小线段长度和
int getMinDistance(int *array, int n, int m) {
int distance[MAXSIZE], maxDistance, minDistance;
sortArray(array, n);
for(int i = 0; i < n - 1; i++) {
distance[i] = array[i + 1] - array[i] - 1;
}
maxDistance = array[n - 1] - array[0] + 1;
sortArray(distance, n - 1);
if( m > n) {
minDistance = n;
}else {
minDistance = maxDistance;
int j = n - 2;
for(int i = 1; i < m; i++) {
if(distance[j] > 0) {
minDistance -= distance[j];
}
j--;
}
}
return minDistance;
}
int main(int argc, const char * argv[]) {
int n, m, a[MAXSIZE], minDistance;
cin >> n >> m;
for(int i = 0; i < n; i++) {
cin >> a[i];
}
minDistance = getMinDistance(a, n, m);
cout << minDistance << "\n";
return 0;
}2-3求解赶作业问题
实验目的：
熟悉贪心算法较为复杂的应用
实验内容：
问题描述:小V上学，老师布置了n个作业，每个作业小v恰好需要一天做完，每个作业都有最后提交时间及其逾期的扣分。请你给出小v做作业的顺序，以便扣最少的分数。
输入:输入包含多个测试用例。每个测试用例第一行为整数 n(1<=n<=100),表示作业数，第2行包括n个整数表示每个作业最后提交的时间(天)，第3行包括n个整数表示每个作业逾期的扣分。以输入 n=0 结束。
输出:每个测试用例对应两行输出，第一行为做作业的顺序(作业编号之间用空格分隔),第2行为最少的扣3分。
输人样例:
3 //3 个作业
1 3 1 //最后提交的时间(天)
6 2 3 //逾期的扣分
0
样例输出:
1 2
3
实验结果截图及分析：
本题仍旧是贪心算法的练习，同样需要进行排序，但是与上面两题不同的是本题根据题意，没办法使用数组直接记录数值，因此这里得采用结构体保存作业序号、截止时间、及逾期需要扣除的分数。
排序的方法为：先根据截止日期进行排序，截止日期小的排在前面，若是截止日期相同，则逾期分数大的排在前面。
然后根据每天只能做一个作业这个规则，依次遍历有序数组中的值是否符合可以做的条件，不可以则将逾期扣除的分数加上，可以则记录作业的序号。
实现核心代码及注释：
// main.cpp
// maxScore
// Created by 小可爱 on 2021/11/4.
//
#include <iostream>
using namespace std;
const int MAXSIZE = 100;
struct homeWork{
//作业序号
int no;
//作业提交截止日期
int deadline;
//分数
int score;
};
//按紧急程度排序，如紧急程度相同，则按分数排序
void sortArray(homeWork *array, int size) {
homeWork temp;
int maxValue;
for(int i = 0; i < size - 1; i++) {
maxValue = i;
for(int j = i + 1; j < size; j++) {
if(array[maxValue].deadline > array[j].deadline) {
maxValue = j;
}else if(array[maxValue].deadline == array[j].deadline) {
if(array[maxValue].score < array[j].score) {
maxValue = j;
}
}
}
temp = array[i];
array[i] = array[maxValue];
array[maxValue] = temp;
}
}
int maxScore(homeWork *array, int size, homeWork *work, int &time) {
int score = 0, sum = 0;
//排序
sortArray(array, size);
for(int i = 0; i < size; i++) {
if(time < array[i].deadline) {
work[time] = array[i];
time++;
}else {
score += array[i].score;
}
}
return score;
}
int main(int argc, const char * argv[]) {
// insert code here...
homeWork homew[MAXSIZE], work[MAXSIZE];
int n, homewNum = 0, time = 0;
while(true) {
cin >> n;
if(n == 0)
break;
//输入截止时间
for(int i = 0; i < n; i++) {
homew[i].no = i + 1;
cin >> homew[i].deadline;
}
//输入逾期扣分
for(int i = 0; i < n; i++) {
cin >> homew[i].score;
}
homewNum = maxScore(homew, n, work, time);
}
for(int i = 0; i < time; i++) {
cout << work[i].no << "\t";
}
cout<< "\n" << homewNum << "\n";
return 0;
}2-4求解袋鼠过河问题
实验目的：
熟悉动态规划问题求解
实验内容：
问题描述：一只袋鼠要从河这边跳到河对岸，河很宽，但是河中间打了很多桩子,每隔一米就有一个，每个桩子上有一个弹簧，袋鼠跳到弹簧上就可以跳的更远。每个弹簧力量不同，用一个数字代表它的力量，如果弹簧的力量为5，就表示袋鼠下一跳最多能够跳 5米，如果为0，就表示会陷进去无法继续跳跃。河流一共n米宽，袋鼠初始在第一个弹簧上面，若跳到最后一个弹簧就算过河了，给定每个弹簧的力量，求袋鼠最少需要多少跳能够到达对岸。如果无法到达，输出一1。
输入描述:输人分两行，第1行是数组长度 n(1<=n<=10000),第2行是每一项的值，用空格分隔。
输出描述:输出最少的跳数，若无法到达输出一1。
输入样例:
5
2 0 1 1 1
样例输出:
4
实验结果截图及分析：
所有动态规划问题求解思路总述：本题以及以下的题均采用动态规划算法求解，
而动态规划算法的四个步骤：1、划分阶段：（按我的理解即为寻找子问题）；2、确定状态和状态变量（即设置初始值）；3、写出状态转移方程（这是这题和以下几题解题思路中我会重点阐述的部分）；4、边界条件（这个具体问题得具体分析了）
另外还有就是序列的求解顺序，也是及其重要的！！！这些题里最后求石子问题与其他的求解序列有不同的写法。
本题求解思路个述：问题的难点主要在于动态方程怎么列，怎么给出动态方程的递推式。
这里用一个动态数组dp记录到达每个柱子需要的最小步数。
例如：题中的取题中的2 0 1 1为例，本题默认到第一根柱子的步数为1，第一根柱子袋鼠的跳力最多可达到2，袋鼠完全可以到达第2根柱子。于是记录到第2根柱子的步数为 1 + 1，到第3根柱子的时候，由于第1根柱子的跳力为2，而第2根柱子的跳力为0，则选取从第1根柱子跳，于是第3根柱子的最小步数为1+1，
由此可以推出动态方程：dp[i] = min{dp[i], dp[j] + 1} (a[j] + j >= i)
实现核心代码及注释：
//
// main.cpp
// riverCrossing
//
// Created by 小可爱 on 2021/11/6.
//
#include <iostream>
using namespace std;
const int MAXSIZE = 10000;
const int MAXNUM = 100000;
//取最小值
int getMin(int num1, int num2) {
return (num1 < num2) ? num1 : num2;
}
//求最小跳数
int getMinSteps(int *distance, int n) {
int steps[MAXSIZE];
//设第0步的初始值为0
steps[0] = 0;
//设置其余步数为一个最大值
for(int i = 1; i <= n; i++) {
steps[i] = MAXNUM;
}
for(int i = 1; i <= n; i++) {
for(int j = 0; j < i; j++) {
if(distance[j] + j >= i) {
steps[i] = getMin(steps[i], steps[j] + 1);
}
}
}
if(steps[n] == MAXNUM) {
return -1;
}else {
return steps[n];
}
}
int main(int argc, const char * argv[]) {
int n, distance[MAXSIZE], steps;
cin >> n;
for(int i = 0; i < n; i++) {
cin >> distance[i];
}
steps = getMinSteps(distance, n);
cout << steps << "\n";
return 0;
}
2-5求解数字何为sum的方法数问题
实验目的：
熟悉动态规划问题
实验内容：
问题描述： 给定一个有n个正整数的数组a和一个整数 sum,求选择数组a中部分数字和为sum 的方案数。若两种选取方案有一个数字的下标不一样，则认为是不同的方案。
输人描述:输人为两行，第1行为两个正整数n(1<n<1000)、sum(1≤sum≤1000),第2行为n个正整数a[i](32 位整数)，以空格隔开。
输出描述:输出所求的方案数。
输入样例:
5 15
5 5 10 2 3
样例输出:
4
实验结果截图及分析：
本题和上一题又所不同，上一题只需要一维的动态数组便可求解，而本题需要二维的动态数组dp[i][j]。按我的理解，需要记录序号，及其值，因此需要二维数组
以下是我根据本题例子所打印出的本题动态数组dp[i][j]记录的值，i记录的是数组中值的位置，j记录的是当前的sum，而dp[i][j] 的值为当前sum的方案总数
用a[i]记录数组中的值
设置初始值：当sum = 0时， 假定其方案数为1
根据这种思路可以推出动态方程：
1. 当 a[i] > j,当前方案数不变，dp[i][j] = dp[i - 1][j]
2. 当 a[i] <= j,求 sum-a[i] 的方案数，之前求得的方案数仍然成立，即 dp[i][j] = dp[i-1][j] + dp[i - 1][j - a[i]]
实现核心代码及注释：
//
// main.cpp
// getSumWayNum
//
// Created by 小可爱 on 2021/11/7.
//
#include <iostream>
using namespace std;
const int MAXSIZE = 1000;
//求使数字和为sum的方法数
int getSumWayNum(int *num, int n, int sum) {
int sums[n + 1][sum + 1];
//设初始值
for(int i = 0; i <= sum; i++) {
sums[0][i] = 0;
}
for(int i = 0; i <= n; i++) {
sums[i][0] = 1;
}
//求方法数
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= sum; j++) {
if(j < num[i -1]) {
sums[i][j] = sums[i - 1][j];
} else {
sums[i][j] = sums[i - 1][j] + sums[i - 1][j - num[i -1]];
}
}
}
//cout << "=======================\n";
/*
for(int i = 0; i <= n; i++) {
for(int j = 0; j <= sum; j++) {
cout <<"["<< i << "][" << j << "]=" <<sums[i][j] << " ";
}
cout << "\n";
}
*/
return sums[n][sum];
}
int main(int argc, const char * argv[]) {
int n, sum, num[MAXSIZE], wayNum;
cin >> n >> sum;
for(int i = 0; i < n; i++) {
cin >> num[i];
}
wayNum = getSumWayNum(num, n, sum);
cout << wayNum << "\n";
return 0;
}2-6求解分饼干问题
实验目的：
熟悉动态规划算法
实验内容：
问题描述：易老师购买了一盒饼干，盒子中一共有k块饼干，但是数字 k有些数位变得模糊了,看不清楚数字具体是多少。易老师需要你帮忙把这k块饼干平分给n个小朋友，易老师保证这盒饼干能平分给n个小朋友。现在需要计算出k有多少种可能的数值。
输人描述:输人包括两行，第1行为盒子上的数值 k,模糊的数位用 X表示，长度小于18(可能有多个模糊的数位),第2行为小朋友的人数n。
输出描述:输出k可能的数值种数，保证至少为1。
输入样例:
9999999999999X
样例输出:
3
实验结果截图及分析：
求饼干问题是所有问题里面我认为最难的，其求解过程不是很容易理解，本题是参考了网上各类讲解才得以做出来的。
大致思路是这样，每个数的余数是固定的，比如7这个数，它的余数就只有0、1、2、3、4、5、6这七种情况
本题的3的余数也只有0、1、2这三种情况
这里我假设 本题求解的饼干数为 1X2
那么我这里我只需要从0～9遍历一边是否符合就行了
首先第1位 为1，1mod3 = 1,
那么到第2位 (1 * 10 + X) mod 3,由于这里的X是未知的，于是得从0～9遍历
这里我再假设一个dp[i][j] 这里的i表示有几位数，j代表余数的取值范围，dp[i][j]代表当余数为j时，前面i位的个数
总的来说，前i - 1位留下来的余数会是0～n-1，那么前面留下来的余数加上目前第i位第数会组成一个新的数，再跟n进行取余会得到新的余数，于是递推式便出来了。
rej = (j * 10 + (ch[i - 1] - ‘0’)) % n
dp[i][rej] += dp[i - 1][j]
实现核心代码及注释：
//
// main.cpp
// getCookiesNum
//
// Created by 小可爱 on 2021/11/7.
//
#include <iostream>
#include <string.h>
#include <string>
using namespace std;
const int MAXSIZE = 100;
int getCookiesNum(string ch, int n) {
//设置一个状态数组
int nums[MAXSIZE][10] = {0}, rej = 0;
//设置初始值
nums[0][0] = 1;
//求所有可能值
for(int i = 1; i <= ch.length(); i++) {
for(int j = 0; j < n; j++) {
//判断数位是否为X
if(ch[i - 1] == 'X') {
for(int k = 0; k <= 9; k++) {
rej = (j * 10 + k) % n;
nums[i][rej] += nums[i - 1][j];
}
}else {
rej = (j * 10 + (ch[i - 1] - '0')) % n;
nums[i][rej] += nums[i - 1][j];
}
}
}
return nums[ch.length()][0];
}
int main(int argc, const char * argv[]) {
string chars;
int n, kindNum;
cin >> chars;
cin >> n;
kindNum = getCookiesNum(chars, n);
cout << kindNum << "\n";
return 0;
}2-7求解小易喜欢的数列问题
实验目的：
熟悉动态规划算法
实验内容：
题目描述
有两个用字符串表示的非常大的大整数,算出他们的乘积，也是用字符串表示。不能用系统自带的大整数类型。
输入描述:
空格分隔的两个字符串，代表输入的两个大整数
输出描述:
输入的乘积，用字符串表示
示例1
输入
复制
72106547548473106236 982161082972751393
输出
复制
70820244829634538040848656466105986748
代码：
实验结果截图及分析：
本题也是用动态规划的思路求解
首先可以先求出这些数所有的数列数，然后再求出不满足小易喜欢数列的数
将总数列数-小易不喜欢数列的数，就可以求得小易喜欢的数列数
本题求解的点在于分析小易不喜欢数的条件，根据题意可以得到小易不喜欢的数列条件为A > B && A % B == 0,便可以轻易求解。
其递推的方式和斐波那契数列的思路类似，只不过是一层一层求解的罢了，不多赘述。
实现核心代码及注释：
//
// main.cpp
// getSeqNum
//
// Created by 小可爱 on 2021/11/8.
//
#include <iostream>
using namespace std;
const int MODNUM = 1000000007;
int getSeqNum(int n, int k) {
int nums[n + 1][k + 1], iSum = 0, dividSum = 0, totalSum = 0;
//初始值
for(int i = 0; i <= n; i++) {
for(int j = 0; j <= k; j++) {
nums[i][j] = 0;
}
}
nums[0][0] = 1;
for(int i = 1; i <= k; i++) {
nums[1][i] = 1;
}
for(int i = 2; i <= n; i++) {
for(int j = 1; j <= k; j++) {
iSum += nums[i - 1][j];
}
//统计不合格的序列数
for(int j = 1; j <= k; j++) {
for(int m = 1; m <= k; m++) {
if(j > m && j % m == 0) {
dividSum += nums[i - 1][m];
}
}
nums[i][j] = (iSum - dividSum) % MODNUM;
dividSum = 0;
}
iSum = 0;
}
for(int i = 1; i <= k; i++) {
totalSum += nums[n][i];
}
return totalSum;
}
int main(int argc, const char * argv[]) {
int n, k, sum;
cin >> n >> k;
sum = getSeqNum(n, k);
cout << sum << "\n";
return 0;
}2-8求解石子合并问题
实验目的：
熟悉动态规划算法
实验内容：
问题描述：有n堆石子排成一排，每堆石子有一定的数量，现要将n堆石子合并成为一堆，合并只能每次将相邻的两堆石子堆成一堆，每次合并花费的代价为这两堆石子的和，经过n-1次合并后成为一堆，求出总代价的最小值。
输人描述:有多组测试数据，输入到文件结束。每组测试数据的第1行有一个整数n表示有n堆石子，接下来的一行有n(0<n<200)个数，分别表示这n堆石子的数目，用空格隔开。
输出描述:输出总代价的最小值，占单独的一行。
输人样例:
3
1 2 3
7
13 7 8 16 21 4 18
样例输出:
9
239
实验结果截图及分析：
本题寻找思路时，我首先确实是用贪心的思路算了一下（由于前面有贪心算法的铺垫），但是我所求出的结果和题例中对不上。
本题还要讲述根据本题的样例，是一个多组测试数据的，这里我仅用输入-1退出程序运行。
由于要交作业了，我简述一下思路
这里用dp[i][j]记录从i到j所需付出的代价， 当i=j时，其值为0，
当我要求dp[i][j] 时，我可以将i 到 j 分成两段，我只需要找到 i 到某个值 + 某个值+1到j 的最小值即可求得dp[i][j]的最小代价，最后它的值得加上i到j这堆石子数量的总和，
于是动态规划数组便呼之欲出了，但是还得强调一下顺序问题，这里得先算相邻的代价，再往大了扩，反之则不可。
实现核心代码及注释：
// main.cpp
// gravelMerge
// Created by 小可爱 on 2021/11/8.
//
#include <iostream>
using namespace std;
const int MAXSIZE = 200;
const int MAXNUM = 99999999;
//最小值
int getMin(int num1, int num2) {
return (num1 <= num2) ? num1 : num2;
}
//求合并石子的最小代价
int gravelMerge(int *gravel, int n) {
int sum[n + 1], minWeight[n + 1][n + 1];
//设置初始值
sum[0] = 0;
for(int i = 0; i < n; i++) {
sum[i + 1] = 0;
for(int j = 0; j <= i; j++) {
sum[i + 1] += gravel[j];
}
}
for(int i = 0; i <= n; i++) {
for(int j = 0; j <= n; j++) {
if(i == j) {
minWeight[i][j] = 0;
}else {
minWeight[i][j] = MAXNUM;
}
}
}
for(int m = 1; m <= n; m++) {
for(int i = 1; i <= n - m; i++) {
int j = i + m;
for(int k = i; k < j; k++) {
minWeight[i][j] = getMin(minWeight[i][j], minWeight[i][k] + minWeight[k + 1][j] + sum[j] - sum[i - 1]);
}
//cout << "[" << i << "][" << j << "]=" << minWeight[i][j] << "\n";
}
}
return minWeight[1][n];
}
int main(int argc, const char * argv[]) {
int n, gravel[MAXSIZE], minPrice;
cin >> n;
while(n != -1) {
for(int i = 0; i < n; i++) {
cin >> gravel[i];
}
minPrice = gravelMerge(gravel, n);
cout << minPrice << "\n";
cin >> n;
}
return 0;
}原文地址：https://blog.csdn.net/weixin_43836257/article/details/143823631
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！