# 算法分析kcsj

**Repository Path**: ZhangYeerui/algorithm-analysis-kcsj

## Basic Information

- **Project Name**: 算法分析kcsj
- **Description**: 算法分析课程设计 阿巴阿巴阿巴阿巴阿巴阿巴阿巴阿巴阿巴
- **Primary Language**: Java
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 2
- **Forks**: 0
- **Created**: 2022-05-29
- **Last Updated**: 2022-12-06

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# 算法分析课程设计

#### 介绍
算法分析课程设计

#### 题目

1. 最少硬币问题（动态规划）

   设有$n$种不同面值的硬币，各硬币的面值存于数组$T[1:n]$中。现要用这些面值的硬币来找钱。可以使用的各种面值的硬币个数存于数组$Coins[1:n]$中。

   对任意钱数$0 \leq m \leq 20001$，设计一个用最少硬币找钱$m$的方法。

   **$\color{blue}{*算法设计:}$**

   对于给定的$1 \leq n \leq 10$，硬币面值数组T和可以使用的各种面值的硬币个数数组$Coins$，以及钱数$m$，$0 \leq m \leq 20001$，计算找钱$m$的最少硬币数。

   **$\color{blue}{*数据输入:}$**

   由文件提供输入数据，文件的第$1$行中只有$1$个整数给出$n$的值，第$2$行起每行$2$个数，分别是$T[j]$和$Coins[j]$。最后$1$行是要找的钱数$m$。

   **$\color{blue}{*结果输出:}$**

   将计算出的最少硬币数输出，问题无解时输出-1。

2. 磁带最优存储问题（贪心算法）

   设有$n$个程序${1, 2,\dots,n}$要存放在长度为$L$的磁带上。程序$i$存放在磁带上的长度是 $l_i,1 \leq i\leq n$。这$n$个程序的读取概率分别是${p_1,p_2,\dots,p_n}$,且$\sum \limits_{i = 1}^{n}p_i=1$。如果将这$n$个程序按${i_1,i_2,\dots,i_n}$的次序存放，则读取程序$i_r$所需的时间$t_r=c*\sum \limits_{k = 1}^{r}p_{ik}l_{ik}$。这$n$个程序的平均读取时间为$\sum \limits_{r = 1}^{n}t_r$。

   磁带最优存储问题要求确定这$n$个程序在磁带上的一个存储次序，使平均读取时间达到最小。

   **$\color{blue}{*算法设计:}$**

   对于给定的*$n$*个程序存放在磁带上的长度和读取概率，试设计一个解此问题的算法，计算*$n$*个程序的最优存储方案，并分析算法的正确性和计算复杂性。

   **$\color{blue}{*数据输入:}$**

   由文件给出输入数据。第$1$行是正整数$n$，表示文件个数。接下来的$n$行中，每行有$2$个正整数$a$和$b$，分别表示程序存放在磁带上的长度和读取概率。实际上第$k$个程序的读取概率$a_k/ \sum \limits_{i=1}^{n}a_i$。对所有输入均假定$c=1$。

   **$\color{blue}{*结果输出:}$**

   将计算出的最小平均读取时间输出。

3. 多处最优服务次序问题（贪心算法）

   设有$n$个顾客同时等待一项服务。顾客$i$需要的服务时间为$t_i,1 \leq i \leq n$。共有$s$处可以提供此项服务。应如何安排$n$个顾客的服务次序才能使平均等待时间达到最小?平均等待时间是*$n$*个顾客等待服务时间的总和除以$n$。 

   **$\color{blue}{*算法设计:}$**

   对于给定的$n$个顾客需要的服务时间和*s*的值，计算最优服务次序。

   **$\color{blue}{*数据输入:}$**

   由文件给出输入数据。第一行有$2$个正整数*$n$*和*$s$*，表示有$n$g个顾客且有*s*处可以提供顾客需要的服务。接下来的$1$行中，有*$n$*个正整数，表示*$n$*个顾客需要的服务时间。

   **$\color{blue}{*数据输出:}$**

   将计算出的最小平均等待时间输出。

4. 部落卫队问题（回溯法）

   原始部落$byteland$中的居民们为了争夺有限的资源，经常发生冲突。几乎每个居民都有他的仇敌。部落酋长为了组织一支保卫部落的队伍，希望从部落的居民中选出最多的居民入伍，并保证队伍中任何$2$个人都不是仇敌。

   **$\color{blue}{*算法设计:}$**

   给定$byteland$部落中居民间的仇敌关系，计算组成部落卫队的最佳方案。

   **$\color{blue}{*数据输入:}$**

   由文件给出输入数据。第$1$行有$2$个正整数$n$和$m$，表示$byteland$部落中有$n$个居民，居民间有$m$个仇敌关系。居民编号为$1,2,\dots,n$。接下来的$m$行中，每行有$2$个正整数$u$和$v$，表示居民$u$与居民$v$是仇敌。

   **$\color{blue}{*结果输出:}$**

   将计算出的部落卫队的最佳组建方案输出。第$1$行是部落卫队的人数；第$2$行是卫队组成$x_i,1 \leq i \leq n$, $x_i=0$表示居民$i$不在卫队中, $x_i=1$表示居民$i$在卫队中。