本文主要是介绍GIS算法基础丨第一周作业，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
问题1：最佳工作序列
有N件工作，输入每件工作的费时、最后完成的期限以及工作的价值，试求可能的一个完成工作序列，使得价值和最大。
/*
* GIS算法第一周作业 luo
*
* 程序功能：有N件工作，输入每件工作的费时、最后完成期限以及工作的价值，
* 试求可能的一个完成工作序列，使价值之和最大。
*
* luo 2024/9/2 最佳工作序列
* 存在问题：代码样例限制了每件工作费时1天
*
* luo 2024/9/3 修改程序使得程序需要考虑每件工作所花费的时间
* 存在问题：从最后期限开始安排工作使得前面有些天数并没有安排工作，而原先排在后面但能够完成得工作无法参与排序
* 改进方法：增加一个否有时间间隙的判断，若间隙之和能够安排下工作，则可以将已经安排好的工作提前
*
* luo 2024/9/4 修改程序改进了昨天存在的问题
*
*/#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h> #define MAX_DAYS 50 // 最大累积工作时长 typedef struct
{char id; // 工作代号 int duration; // 费时 int deadline; // 最后期限 int value; // 价值
} Job;void profitSort(Job* jobs, int n); // 用于工作收益效率的降序排序
int findMaxDDL(Job* jobs, int n); // 用于寻找最晚期限
void printResult(char result[], bool slot[], int n); // 用于打印最佳工作序列结果
void findBestJobScheduling(Job* jobs, int n); // 用于寻找最佳工作序列的函数 int main()
{int n;printf("请输入工作数量: ");if (scanf("%d", &n) != 1 || n <= 0) {printf("输入无效，请输入一个正整数。\n");return 1;}Job* jobs = (Job*)malloc(n * sizeof(Job));if (jobs == NULL){printf("内存分配失败。\n");return 1;}for (int i = 0; i < n; i++){printf("请输入第%d个工作的代号、费时、最后期限以及价值:\n", i + 1);if (scanf(" %c %d %d %d", &jobs[i].id, &jobs[i].duration, &jobs[i].deadline, &jobs[i].value) != 4){printf("输入格式错误。\n");free(jobs);return 1;}}findBestJobScheduling(jobs, n);free(jobs);return 0;
}void profitSort(Job* jobs, int n)
{for (int i = 0; i < n - 1; i++){for (int j = 0; j < n - 1 - i; j++){double profitA = (double)jobs[j].value / jobs[j].deadline;double profitB = (double)jobs[j + 1].value / jobs[j + 1].deadline;if (profitA < profitB){Job temp = jobs[j];jobs[j] = jobs[j + 1];jobs[j + 1] = temp;}}}
}int findMaxDDL(Job* jobs, int n)
{int maxDDL=jobs[0].deadline;for (int i = 1; i < n; i++){if (jobs[i].deadline > maxDDL){maxDDL = jobs[i].deadline;}}return maxDDL;
}void printResult(char result[], bool slot[], int n)
{printf("最佳工作序列为：");for (int i = 0; i < n; i++){if (result[i] != result[i + 1] || result[i + 1] == 0){printf("%c ", result[i]);}}
}void findBestJobScheduling(Job* jobs, int n)
{// 1、按工作的profit进行升序排序（冒泡排序）profitSort(jobs, n);// 2、找到最晚期限int max_DDL = findMaxDDL(jobs, n);char result[MAX_DAYS] = { 0 }; // 用于存储工作序列结果 bool slot[MAX_DAYS] = { false }; // 用于标记特定日期是否有工作安排int value_sum = 0; // 用于记录最终的价值之和// 3、寻找最佳工作序列 for (int i = 0; i < n; i++){int record = 0; //计算第i个工作最后期限前有多少天为空for (int j = jobs[i].deadline - 1; j >= 0 && slot[j] == false; j--){record++;}if (record >= jobs[i].duration) // 若空出的天数足够用于安排工作{for (int k = jobs[i].deadline - 1; k >= jobs[i].deadline - jobs[i].duration; k--){result[k] = jobs[i].id;slot[k] = true;}value_sum += jobs[i].value;}else // 若当前期限前空出天数无法安排工作{//记录ddl前空余的天数int valible_days = 0;for (int k = 0; k <jobs[i].deadline; k++){if (slot[k] == false){valible_days++;}}if (valible_days >= jobs[i].duration) // 若空余天数能安排下该工作 {int daysMoved = 0;// 将之前安排的工作提前 for (int k = 0; k < jobs[i].deadline; k++){while(slot[k] == false && daysMoved < jobs[i].duration) // 若当前时间空余则将之后的工作往前{for (int pos = k; pos < jobs[i].deadline; pos++){result[pos] = result[pos + 1];slot[pos] = slot[pos + 1];}daysMoved++;}}//将新的工作安排在ddl之前for (int k = jobs[i].deadline - 1; k >= jobs[i].deadline - jobs[i].duration; k--){result[k] = jobs[i].id;slot[k] = true;}value_sum += jobs[i].value;}}}// 4、输出结果 printf("\n");printResult(result, slot, max_DDL);printf("\n");printf("最终价值总和为%d", value_sum);}问题2：最长路径问题
现有一个nxn大小的格网，其中有些格子无法走通，已知出发点为（0，0），问在这个格网中从起点开始直到边界走过的最长路径（格子数）为多少？
要求：
①不能走回头路，格子不重复
②前进方向为上、下、左、右，不能斜着走
这篇关于GIS算法基础丨第一周作业的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
