当前位置：首页 > news >正文

算法设计作业

news 2024/11/29 3:36:17

第四章（贪心算法）

4.1最短路径-Dijkstra

输入格式:

输入的第一行给出城市数目N (1≤N≤10)和道路数目M和1（表示有向图）或0（表示无向图）；

接下来的M行对应每个城市间来往所需时间，每行给出3个正整数，分别是两个城市的编号（从1编号到N）和来往两城市间所需时间。最后一行给出一个编号，表示从此编号地点出发。

输出格式:

输出从特定地点出发到达所有城市（按编号1-编号N顺序输出）的距离（用编号1->编号**: 表示），如果无路，请输出no path。每个城市占一行。

输入样例:

输出样例:

1->1:0
1->2:2
1->3:14
1->4:8
1->5:no path

思路

1.使用vector创建动态数组储存图，记得区分有向无向图；

2.dijkstra算法：

(1)源点集合S，初始源点为起点v

(2)需要将剩余n-1个点放入集合S表示完成任务

(2).1 循环n-1次找剩余n-1个源点

(2).2 找新源点s放入S（新源点就是dist[s]最小），标记新源点vis[s]=1；

(2).3更新距离初源点v的距离即dist[]：

找除了S里面的源点且与新源点s相连的点j，比较dist[s]+grap[s][j]和dist[j]的大小，然后更新。

代码

#include<bits/stdc++.h>
using namespace std;
#define ff 11
#define mmax INT_MAX

void dijkstra(int n,int v,vector<vector<int>>& grap){
vector<int> vis(ff,0);
vector<int> dist(ff,mmax);

for(int i=1;i<=n;i++){
if(grap[v][i]!=mmax){
dist[i]=grap[v][i];
}
}
vis[v]=1;
dist[v]=0;

for(int j=1;j<n;j++){
int len=mmax;
int s=v;
for(int i=1;i<=n;i++){
if(!vis[i]&&dist[i]<len){
len=dist[i];
s=i;
}
}
vis[s]=1;

for(int k=1;k<=n;k++){
if(!vis[k]&&grap[s][k]!=mmax){
int newlen=grap[s][k]+dist[s];
if(newlen<dist[k]){
dist[k]=newlen;
}
}
}
}
for(int i=1;i<=n;i++){
if(dist[i]==mmax) cout<<v<<"->"<<i<<":no path"<<endl;
else cout<<v<<"->"<<i<<":"<<dist[i]<<endl;
}
}

int main(){
int n,m,x;
cin>>n>>m>>x;
vector<vector<int>> grap(ff,vector<int>(ff,mmax));
for(int i=0;i<m;i++){
int u,v,w;
cin>>u>>v>>w;
grap[u][v]=w;
if(!x){
grap[v][u]=w;
}
}
int start;
cin>>start;
dijkstra(n,start,grap);
}

扩展

输出路线：

在更新dist[]处添加：

for(int k=1;k<=n;k++){
if(!vis[k]&&grap[s][k]!=mmax){
int newlen=grap[s][k]+dist[s];
if(newlen<dist[k]){
dist[k]=newlen;

pre[k]=s;
}
}

pre[k]=s表示k的前继点是s（！！！记得定义pre[]数组并初始化为0或者其他随便哈）

输出代码：

int end;//终点

int k=pre[end];

while(k!=0){ //因为我初始化了噻，前继点为0表示到头啦！

cout<<k;

k=pre[k];

}

4.2删数问题

给定n位正整数a，去掉其中任意k≤n 个数字后，剩下的数字按原次序排列组成一个新的正整数。对于给定的n位正整数a和正整数 k，设计一个算法找出剩下数字组成的新数最小的删数方案。如果数字最前面有0不输出。

输入格式:

第 1 行是1 个正整数 a。第 2 行是正整数k。

输出格式:

输出最小数。

输入样例:

在这里给出一组输入。例如：

178543 
4

5001 
1

123456 
2

109 
1

输出样例:

在这里给出相应的输出。例如：

思路

按照数字特点，从左往右，左边数字越小整体越小

所以两种情况：

（1）整数每个数字从左往右递减，那么减掉最右边的数字可以达到题目要求。

（2）如果整数每个数字无序，那边一共循环n次（删n个数字），找出非递减的数字（即左边数字大于右边数字）删掉即可。

最后：如删数后出现数字串为009等情况，记得抹零。

代码

#include<bits/stdc++.h>
using namespace std;

int main(){
int n;
string s;
cin>>s>>n;
for(int i=0;i<n;i++){
for(int j=0;j<s.size();j++){
if(s[j]>s[j+1]||j==s.size()-1){
s.erase(s.begin()+j);
break;
}
}
}
while(s[0]=='0') s.erase(s.begin());
cout<<s;
return 0;
}

4.3最优分解问题

设 n 是一个正整数。现在要求将 n 分解为若干个互不相同的自然数的和，且使这些自然数的乘积最大。

输入格式:

文件的第 1 行是正整数 n。

输出格式:

将计算出的最大乘积输出

输入样例:

输出样例:

思路

如果a+b=n，则|a-b|越小，那么ab越大，可以将n分解成从2开始的连续自然数的和，如果到某个数时不够分（比如下一个分解数是4，但因为分解完3只剩2），那么把2往会加（即原路返回每个加1，尽量减小|a-b|）

代码

#include<bits/stdc++.h>
using namespace std;

int find(int n){
vector<int> a(2*n);
if(n<=4) return n-1;

int i=0;
int k=2;
while(n>=k){
a[i]=k;
i++;
n-=k;
k++;
}
int p=i;

while(n!=0){
a[i-1]++;
n--;
i--;
}
int num=1;
for(int j=0;j<p;j++){
num*=a[j];
}
return num;
}

int main(){
int n;
cin>>n;
int mmax=find(n);
cout<<mmax;
}

4.4 程序存储问题

设有n 个程序{1,2,…, n }要存放在长度为L的磁带上。程序i存放在磁带上的长度是 li，1≤i≤n。程序存储问题要求确定这n 个程序在磁带上的一个存储方案，使得能够在磁带上存储尽可能多的程序。对于给定的n个程序存放在磁带上的长度，计算磁带上最多可以存储的程序数。

输入格式:

第一行是2 个正整数，分别表示文件个数n和磁带的长度L。接下来的1行中，有n个正整数，表示程序存放在磁带上的长度。

输出格式:

输出最多可以存储的程序数。

输入样例:

在这里给出一组输入。例如：

6 50 
2 3 13 8 80 20

输出样例:

在这里给出相应的输出。例如：

思路

需要放入最多的程序，即尽量安排空间需求小的程序。（排序从小到大）

代码

#include<bits/stdc++.h>
using namespace std;

int main(){
int n,l;
cin>>n>>l;
vector<int> a(n);
for(int i=0;i<n;i++){
cin>>a[i];
}
sort(a.begin(),a.end());

int pp=a[0];
int num=0;
int i=0;
while(l>0&&l>=pp){
l-=pp;
num++;
i++;
pp=a[i];
}
cout<<num;
}

扩展

vector数组排序：

1.从小到大

sort(name.begin(),name.end());

name.begin()表示指向数组头的迭代器，name.end()表示指向数组尾下一个位置的迭代器，该式表示将叫name的vector元素按从小到大进行升序排序。

2.从大到小

sort(name.rbegin(),name.rend());

name.rbegin()表示指向数组尾的迭代器，name.rend()表示指向数组头前一个位置的迭代器，该式表示将叫name的vector元素按从大到小进行降序排序。

3.自定义

sort(res.begin(),res.end(),[&](const typename&a,const typename&b)->bool{
return (输入你的排序标准);
});

4.5最优合并问题

给定k 个排好序的序列, 用 2 路合并算法将这k 个序列合并成一个序列。
假设所采用的 2 路合并算法合并 2 个长度分别为m和n的序列需要m+n-1 次比较。试设
计一个算法确定合并这个序列的最优合并顺序，使所需的总比较次数最少。
为了进行比较，还需要确定合并这个序列的最差合并顺序，使所需的总比较次数最多。

输入格式:

第一行有 1 个正整数k，表示有 k个待合并序列。
第二行有 k个正整数，表示 k个待合并序列的长度。

输出格式:

输出最多比较次数和最少比较次数。

输入样例:

在这里给出一组输入。例如：

4
5 12 11 2

输出样例:

在这里给出相应的输出。例如：

78 52

思路

类似哈夫曼编码，最少比较即从较小个待合并序列开始合并，最多反之。

代码

#include<bits/stdc++.h>
using namespace std;

int mergemin(vector<int>& a,int n){
int num=0;
int m=n;
while(m>1){
m--;
num+=(a[0]+a[1]-1);
a[0]+=a[1];
a.erase(a.begin()+1);
sort(a.begin(),a.end()); //!!! 必须要sort，因为新合并的序列长度可能比后面的序列长度长。
}
return num;
}

int mergemax(vector<int>& a,int n){
int num=0;
int m=n;
while(m>1){
m--;
num+=(a[0]+a[1]-1);
a[0]+=a[1];
a.erase(a.begin()+1);
sort(a.rbegin(),a.rend());
}
return num;
}

int main(){
int n;
cin>>n;
vector<int> a(n);
vector<int> b(n);
for(int i=0;i<n;i++) cin>>a[i];
for(int j=0;j<n;j++) b[j]=a[j];

sort(a.begin(),a.end());
sort(b.rbegin(),b.rend());

int mmax=mergemax(b,n);
int mmin=mergemin(a,n);
cout<<mmax<<" "<<mmin;
return 0;
}

sort用法可以参考4.4的扩展

4.6排队接水

有n个人在一个水龙头前排队接水，假如每个人接水的时间为Ti，请编程找出这n个人排队的一种顺序，使得n个人的平均等待时间最小。

输入格式:

共两行，第一行为n(1≤n≤1000)；第二行分别表示第1个人到第n个人每人的接水时间T1，T2，…，Tn，每个数据之间有1个空格。

输出格式:

输出为这种排列方案下的平均等待时间(输出结果精确到小数点后两位)。

输入样例:

10
56 12 1 99 1000 234 33 55 99 812

输出样例:

291.90

思路

贪心算法：要使平均等待时间最短，即节水快的先接。

2等待1 ！！！记得最后总时间要加上第一个人接水的时间喔

3等待1+2

4等待(1+2)+3

5等待（1+2+3)+4

.........

所以可以用循环合并n-2次（最后剩下两个不用合并噻）

注意开头和结尾噻！！！

代码

#include<bits/stdc++.h>
using namespace std;

int main(){
int n;
int time=0;
cin>>n;
vector<int> a(n);
for(int i=0;i<n;i++) cin>>a[i];
sort(a.begin(),a.end());
int p=a[0];
while(a.size()>2){
time+=(a[0]+a[1]);
a[0]+=a[1];
a.erase(a.begin()+1);
}
double aver=(double)(time+p)/n;
cout<<fixed<<setprecision(2)<<aver;
}

4.7选点问题

数轴上有n个闭区间[ai, bi]。取尽量少的点，使得每个区间内都至少有一个点（不同区间内含的点可以是同一个）。

输入格式:

第一行一个数字n，表示有n个闭区间。
下面n行，每行包含2个数字，表示闭区间[ai, bi]

输出格式:

一个整数，表示至少需要几个点

输入样例:

在这里给出一组输入。例如：

输出样例:

在这里给出相应的输出。例如：

思路

题目就是解决用最少的点覆盖所有区间：即若有交集的区间，点放交集里头，没交集的区间单独开一个点丢进去。

如何定义是否交集？

1.先把区间按照end从小到达排序

2.以第一个区间end为标准end开始计数

3.如果下一个区间start<=end（说明交集，计数+1）

4.如果下一区间start>end（说明不交集），更新end

5.循环以上即可^_^

代码

#include<bits/stdc++.h>
using namespace std;

struct qujian{
int start;
int end;
};

bool compare(const qujian&a,const qujian&b){
return a.end<b.end;
}

int main(){
int n;
cin>>n;
vector<qujian> qu(n);
for(int i=0;i<n;i++){
cin>>qu[i].start>>qu[i].end;
}
sort(qu.begin(),qu.end(),compare);

int newend=qu[0].end;
int num=1;
for(int i=1;i<n;i++){
if(qu[i].start>newend){
num++;
newend=qu[i].end;
}
}
cout<<num;
}

4.8 汽车加油问题

一辆汽车加满油后可行驶 n公里。旅途中有若干个加油站。设计一个有效算法，指出应
在哪些加油站停靠加油，使沿途加油次数最少。

输入格式:

第一行有 2 个正整数n和 k（k<=1000 )，表示汽车加满油后可行驶n公里，且旅途中有 k个加油站。
第二行有 k+1 个整数，表示第 k 个加油站与第k-1 个加油站之间的距离。
第 0 个加油站表示出发地，汽车已加满油。
第 k+1 个加油站表示目的地。

输出格式:

输出最少加油次数。如果无法到达目的地，则输出“No Solution!”。

输入样例:

7 7
1 2 3 4 5 1 6 6

输出样例:

思路

够油不加，不够就加呗

代码

#include<bits/stdc++.h>
using namespace std;

int main(){
int n,k;
cin>>n>>k;
vector<int> d(k+1);
for(int i=0;i<k+1;i++){
cin>>d[i];
if(d[i]>n){
cout<<"No Solution!";
return 0;
}
}

int num=0;
int len=n;
for(int i=0;i<k+1;i++){
if(len>d[i]){
len-=d[i];
}
else{
num++;
len=n-d[i];
}
}
cout<<num;
return 0;
}

第五章（回溯）

5.1 0-1背包（n<=10）

给定n(n<=10)种物品和一个背包。物品i的重量是wi，价值为vi，背包的容量为C(C<=1000)。问:应如何选择装入背包中的物品，使得装入背包中物品的总价值最大? 在选择装入背包的物品时，对每种物品i只有两个选择：装入或不装入。不能将物品i装入多次，也不能只装入部分物品i。可以不剪枝。

输入格式:

共有n+1行输入：第一行为n值和c值，表示n件物品和背包容量c；接下来的n行，每行有两个数据，分别表示第i(1≤i≤n)件物品的重量和价值。

输出格式:

输出装入背包中物品的最大总价值。

输入样例:

输出样例:

思路

01背包属于找最优解问题，用回溯法需要构造解的子集树，选为1，不选为0。可以顺序依次考虑每个物品，这样就形成了一棵解空间树：基本思想就是遍历这棵树，以枚举所有情况，最后进行判断，如果重量不超过背包容量，且价值最大的话，该方案就是最后的答案。

！！！这是不剪枝方法，只适合物品较少的情况。

逐层返回：当back(m)执行return时，控制权返回给调用它的back(m-1)。back(m-1)会继续执行它自己的代码（如果有的话），在尝试放入或不放入索引为m-1的物品之后，它也会遇到一个return语句（可能是隐式的，即函数执行完毕自然返回），然后将控制权返回给back(m-2)，依此类推。
回到初始调用点：最终，这个过程会一直持续到back(1)执行完毕并返回。此时，控制权返回到main函数中的back(1);之后的代码行。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 11;

int n, c;
vector<int> weight(N), value(N);
vector<int> vis(N, 0);
int maxvalue = 0;
int cv = 0, cw = 0;

void back(int id){
if(id>n){
if(cv>maxvalue) maxvalue=cv;
return;
}

if(cw+weight[id]<=c){
cw+=weight[id];
cv+=value[id];
back(id+1);
cw-=weight[id];
cv-=value[id];
}

back(id+1);
}

int main() {
cin >> n >> c;
for (int i = 1; i <= n; i++) {
cin >> weight[i] >> value[i];
}
back(1); // 从第一个物品开始搜索
cout << maxvalue << endl;
return 0;
}

5.2 部落卫队问题

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

输入格式:

第一行两个正整数n和m，表示byteland部落中有n个居民，居民间有m个仇敌关系， 0<n<200, 0<m<6000。居民编号为1,2,…,n。接下来输入m行中，每行正整数u和v，表示居民u和居民v是仇敌。

输出格式:

输出部落卫队最佳组建方案中包含的居民人数。之后逐个输出卫队组成xi, 1<=i<=n, xi=0表示居民i不在卫队中，xi=1表示居民i在卫队中。

输入样例:

输出样例:

3
1 0 1 0 0 0 1

思路

跟背包啥的一样

代码

#include<bits/stdc++.h>
using namespace std;

int n,m;
vector<vector<int>> amy;
vector<int> xi;
vector<int> cxi;
int mmax=0;

void back(int id,int size){
if(id>n){
if(size>mmax){
mmax=size;
for(int i=1;i<=n;i++){
xi[i]=cxi[i];
}
}
return ;
}

int add=1;
for(int j=1;j<id;j++){
if(cxi[j]&&amy[id][j]){
add=0;
break;
}
}

//选

if(add){
cxi[id]=1;
back(id+1,size+1);
cxi[id]=0;
}

//不选

back(id+1,size);
}

int main(){
cin>>n>>m;
amy.resize(n+1,vector<int>(n+1,0));
xi.resize(n+1);
cxi.resize(n+1);
for(int i=0;i<m;i++){
int u,v;
cin>>u>>v;
amy[u][v]=1;
amy[v][u]=1;
}

back(1,0);
cout<<mmax<<endl;
for(int i=1;i<=n;i++){
cout<<xi[i]<<" ";
}
return 0;
}

5.3子集和问题

设集合S={x1,x2,…,xn}是一个正整数集合，c是一个正整数，子集和问题判定是否存在S的一个子集S1，使S1中的元素之和为c。试设计一个解子集和问题的回溯法，并输出利用回溯法在搜索树（按输入顺序建立）中找到的第一个解。

输入格式:

输入数据第1行有2个正整数n和c，n表示S的大小，c是子集和的目标值。接下来的1行中，有n个正整数，表示集合S中的元素。
是子集和的目标值。接下来的1 行中，有n个正整数，表示集合S中的元素。

输出格式:

输出利用回溯法找到的第一个解，以空格分隔，最后一个输出的后面有空格。当问题无解时，输出“No Solution!”。

输入样例:

在这里给出一组输入。例如：

5 10
2 2 6 5 4

输出样例:

在这里给出相应的输出。例如：

2 2 6

思路

回溯法找解：

1.题目说找到的第一个解，所以先选排在前面的元素，及按照元素顺序展开01完全二叉树，跟5.1，5.2题一样的。

2.回溯back（t,sum），t代表第x个元素，sum代表之前选了元素的总和。

3.回溯流程：

(1）选前判断：sum>m，回溯去掉不要它

（2）选前判断：sum=m，是我们要的结果，因为要第一个结果，所以需要flag标记。一旦找到第一个结果，一路回溯，回到main中的back结束回溯

（3）所有元素遍历完（t=n）：如果sum=m，flag=1，一路回溯到main，如果sum<m，继续找。

（4）选

sum+；

记录此元素s1[t]（t代表层数且第x个元素，所以可以直接用t）

后面回溯记得sum-且去掉s1[t]标记

（5）不选

直接t+1即可，sum不变

代码

#include<bits/stdc++.h>
using namespace std;

int n,m;
vector<int> s;
vector<int> s1;
int flag=0;

void back(int t,int sum){
if(sum>m) return;

if(flag) return;

if(t>n){
if (sum == m) {
for (int i = 1; i <=n; ++i) {
if (s1[i]!=-1)
cout << s1[i] << " ";
}
flag = 1;
}
return;
}

//选
sum+=s[t];
s1[t]=s[t];
back(t+1,sum);
sum-=s[t];
s1[t]=-1;

//不选
back(t+1,sum);
}

int main(){
cin>>n>>m;
s.resize(n+1);
s1.resize(n+1,-1);
int pp=0;
for(int i=1;i<=n;i++){
cin>>s[i];
pp+=s[i];
}

if (pp < m) {
cout << "No Solution!";
return 0;
}

back(1,0);

if (!flag)
cout << "No Solution!";
return 0;
}

5.4 旅行售货员

某售货员要到若干城市去推销商品，已知各城市之间的路程(或旅费)。他要选定一条从驻地出发，经过每个城市一遍，最后回到驻地的路线，使总的路程（或总旅费）最小。

输入格式:

第一行为城市数n

下面n行n列给出一个完全有向图，如 i 行 j 列表示第 i 个城市到第 j 个城市的距离。

输出格式:

一个数字，表示最短路程长度。

输入样例:

输出样例:

思路

有（n-1）!条可选路线

代码可以更简洁，当n过大时，最好剪枝，甚至回溯法不适合。

代码

#include<bits/stdc++.h>
using namespace std;

int n;
vector<vector<int>> grap;
vector<int> x; // 存储当前路径上的城市
vector<int> vis;
int cl = 0;
int mminlen =INT_MAX;

void back(int t) {
if (t==n) {
if(cl+grap[x[n-1]][0]<mminlen) mminlen=cl+grap[x[n-1]][0];
return;
}

for(int i=0;i<n;i++){
if (!vis[i]&&grap[x[t-1]][i] != 0){
cl += grap[x[t-1]][i];
x[t] = i;
vis[i] =1;
cout<<t<<":"<<i<<endl;
back(t + 1);
vis[i] =0;
cl -= grap[x[t-1]][i];
cout<<" back:"<<i<<endl;
}
}
}

int main() {
cin >> n;
grap.resize(n, vector<int>(n, 0));
x.resize(n);
vis.resize(n,0);

for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cin>>grap[i][j];
}
}

x[0] = 0;
vis[0] =1;

if(n==1){
cout<<0;
return 0;
}

back(1);
cout << mminlen << endl;

return 0;
}