考前打算把书上的代码和之前的作业过一遍。
递归与分治问题 阶乘int factorial(int n)
{
if(n==0)return 1;
return n*factorial(n-1);
}
斐波那契数列
int fibonacci(int n)
{
if(n<=1)return 1;
return fibonacci(n-1)+fibonacci(n-2);
}
全排列问题
【问题描述】对n个整数进行全排列
【输入形式】在屏幕上输入若干个整数，各数间都以一个空格分隔。
【输出形式】按照顺序每行输出一种排列方式
【样例输入】
1 2 3
【样例输出】
1 2 3
1 3 2
2 1 3
2 3 1
3 2 1
3 1 2
【样例说明】
输入：三个整数，分别为1,2,3，以空格分隔。
输出：按照顺序每行输出一种排列方式，以空格分隔
【评分标准】根据输入得到准确的输出
#includeusing namespace std; inline void Swap(int &a,int &b) { int tmp = a; a = b; b = tmp; } void perm(vector list,int k,int m) { if(k==m) { //只剩下一个元素 for(int i=0;i<=m;i++) { cout << list[i] << ' '; } cout << endl; } else { for(int i=k;i<=m;i++) { Swap(list[k],list[i]); perm(list,k+1,m); Swap(list[k],list[i]); } } } int main() { vector list; int num,n=0; while(cin >> num) { list.push_back(num); n++; if(cin.get()=='n')break; } perm(list,0,n-1); return 0; }
算法Perm(list,k ,m)递归地产生所有前缀是list[0:k一1],且后缀是list[k：m]的全排列的所有排列。函数调用Perm(list,0,n一1)则产生list[0:n一1]的全排列。
整数划分问题得到划分的种数：
int q(int n,int m)
{
if((n<1)||(m<1))return 0;
if((n==1)||(m==1))return 1;
if(n
汉诺塔
void hanoi(int n,int a,int b,int c)
{
//将塔座a上自下而上由大到小叠放的n个圆盘依规则移动到b
if(n>0)
{
hanoi(n-1,a,c,b);
move(a,b);//move是自带函数
hanoi(n-1,c,b,a);
}
}
二分搜索
【问题描述】使用二分搜索方法，在有序数组中寻找特定的元素。说明：在数组a的编号[left, right]范围内求取中间元素编号mid时，mid=floor((left+right)/2)。
【输入形式】在屏幕上输入若干个从小到大排列的互不相同的整数，各数间都以一个空格分隔。再输入要寻找的元素key，其中min
【输出形式】输出每次搜索的所在范围内的整数。若有序数组中存在该特定元素，则输出该元素在数组中的位置；若不存在，则输出0。
【样例1输入】
15 17 18 22 35 51 60 88 90 100
18
【样例1输出】
15 17 18 22 35 51 60 88 90 100
15 17 18 22
18 22
3
【样例1说明】
输入：10个有序整数，以空格分隔。要寻找的特定元素为18。
输出：第一至第三行为三次搜索的所在范围内的整数。第四行为3，表示特定元素18在有序数组第3个位置。
【样例2输入】
15 17 18 22 35 51 60 88 90 100
35
【样例2输出】
15 17 18 22 35 51 60 88 90 100
5
【样例2说明】
输入：10个有序整数，以空格分隔。要寻找的特定元素为35。
输出：第一行为一次搜索的所在范围内的整数，第一次就搜索到了要寻找的特定元素35。第二行为5，表示特定元素35在有序数组第5个位置。
【样例3输入】
15 17 18 22 35 51 60 88 90 100
70
【样例3输出】
15 17 18 22 35 51 60 88 90 100
51 60 88 90 100
51 60
0
【样例3说明】
输入：10个有序整数，以空格分隔。要寻找的特定元素为70。
输出：第一至第三行为三次搜索的所在范围内的整数。第四行为0，表示特定元素70在有序数组不存在。
【评分标准】根据输入得到准确的输出
#include
using namespace std;
int main(){
vectornums;
int tmp;
cin>>tmp;
nums.push_back(tmp);
while(cin.get()!='n'){
cin>>tmp;
nums.push_back(tmp);
}
int key;
int l,r,mid,pos=0;
cin>>key;
l=0;
r=nums.size()-1;
for(int i=l;i<=r;i++)
cout<nums[r]||key
棋盘覆盖
【问题描述】使用递归与分治策略解决棋盘覆盖问题
【输入形式】在屏幕上输入棋盘大小及特殊方格所在行号和列号。
【输出形式】输出使用L型骨牌进行棋盘覆盖结果。
【样例1输入】
2
1 2
【样例1输出】
2 -1 3 3
2 2 1 3
4 1 1 5
4 4 5 5
【样例说明】
输入：第一行输入整数k表示棋盘大小为2的k次幂，若k为2，则棋盘大小为4行4列；若k为3，则棋盘大小为8行8列。第二行输入特殊方格所在的行号和列号，以空格分隔，当前输入的：1 2，表示特殊方格在棋盘的第1行第2列。2<=k<=3。
输出：使用L型骨牌进行棋盘覆盖结果，由3个相同的数表示同一个L型骨牌，不同的骨牌用不同的数字表示。数字的大小表示棋盘覆盖的顺序。特殊方格在棋盘的第1行第2列，用-1表示。各整数间以空格分隔。
【评分标准】根据输入得到准确的输出
#include
using namespace std;
int tile = 1;
int board[100][100];
void chessboard(int tr,int tc,int dr,int dc,int size)
{
if(size==1)return;
int t = tile++;
int s = size/2;
if(dr=tc+s)chessboard(tr,tc+s,dr,dc,s);
else
{
board[tr+s-1][tc+s] = t;
chessboard(tr,tc+s,tr+s-1,tc+s,s);
}
if(dr>=tr+s&&dc=tr+s&& dc>=tc+s)chessboard(tr+s,tc+s,dr,dc,s);
else
{
board[tr+s][tc+s] = t;
chessboard(tr+s,tc+s,tr+s,tc+s,s);
}
}
int main()
{
int k;
cin >> k;
k = pow(2,k);
int x,y;
cin >> x >> y;
board[x-1][y-1] = -1;
chessboard(0,0,x-1,y-1,k);
for ( int i=0; i
合并排序
【问题描述】使用递归合并排序算法对若干整数进行排序。说明：在数组a的编号[left, right]范围内求取中间元素编号mid时，mid=floor((left+right)/2)。
【输入形式】在屏幕上输入若干整数，各数间都以一个空格分隔。
【输出形式】输出递归函数MergeSort调用的次数和最终从小到大排序好的结果。
【样例输入】
48 38 65 97 76 13 27
【样例输出】
13
13 27 38 48 65 76 97
【样例说明】
输入：7个整数，以空格分隔。
输出：第一行输出递归函数MergeSort调用的次数，第二行输出最终从小到大排序好的结果，整数间以一个空格分隔。
【评分标准】根据输入得到准确的输出
#include
using namespace std;
int cnt=0;//计数器
void copy(int a[],int b[],int l,int r)
{
for(int i=l;i<=r;i++)
{
a[i] = b[i];
}
}
void meg(int a[],int b[],int l,int m,int r)
{
// cout << 'i' << endl;
int i = l,j = m+1,k=l;
while((i<=m)&&(j<=r))
{
if(a[i] nums;
int tmp;
cin >> tmp;
nums.push_back(tmp);
while(cin.get()==' ')
{
cin >> tmp;
nums.push_back(tmp);
n++;
}
// cout << n <
快速排序
【问题描述】每次划分时都以最后一个元素为划分基准，使用快速排序算法对若干整数进行排序，其中分解函数PARTITION以课件中的算法（1）为准。
【输入形式】在屏幕上输入若干整数，各数间都以一个空格分隔。
【输出形式】输出递归函数调用的次数，以及从小到大的排序结果。
【样例输入】
48 38 65 97 76 13 27
【样例输出】
9
13 27 38 48 65 76 97
【样例说明】
输入：7个整数，以空格分隔。
输出：第一行输出递归函数QUICKSORT调用的次数为9。第二行输出从小到大的排序结果，以空格分隔。
【评分标准】根据输入得到准确的输出
#include
#include
#include
using namespace std;
int cnt=0;
int par(vector &a,int p,int r)
{
int i=p-1;
for(int j=p;j list;
int temp;
//这里输入很神奇不能像之前一样输入了
string s;
stringstream ss;
getline(cin,s);
ss<> temp)
{
list.push_back(temp);
}
int n = list.size();
sort(list,0,n-1);
cout << cnt << endl;
for(int i=0;i
线性时间选择
【问题描述】每次都是优化选出一个元素（分组后的中位数）为划分基准，在线性时间内寻找第i小元素。提示：分组时的组的个数为n/5的向下取整；分组后的中位数取第（num_group/2向上取整）小的元素。
【输入形式】在屏幕上输入若干整数，各数间都以一个空格分隔。再输入要寻找的元素是数组从小到大顺序中第几个位置。
【输出形式】输出第一次划分找到的基准元素以及数组从小到大顺序中要寻找的那个位置的元素。
【样例输入】
15
2 9 8 0 7 10 1 12 3 14 5 13 6 11 4
3
【样例输出】
7
2
【样例说明】
输入：15个整数，以空格分隔。要寻找第3小元素。
输出：
7，表示第一次划分得到的基准元素是7。
2，表示第3小元素为2。
【评分标准】根据输入得到准确的输出。
#include
#include
using namespace std;
int flag = 1,a[1005];
void swap(int &a,int &b)
{
int temp = b;
b = a;
a = temp;
}
int par(int a[],int p,int r,int x)
{
int pos = p;
for(int i=p;i<=r;i++)//需要额外考虑是否等于x
if(a[i]==x)
{
pos=i;
break;
}
swap(a[p],a[pos]);
int i=p,j=r+1;
while(1)
{
while(a[++i]x);
if(i>=j)break;
swap(a[i],a[j]);
}
a[p] = a[j];
a[j] = x;
return j;
}
int select(int a[],int p,int r,int k)
{
if(r-p+1<5)
{
//简单排序
sort(a+p,a+r+1);
return a[p+k-1];
}
for(int i=0;i<=(r-p-4)/5;i++)
{
sort(a+p+5*i,a+p+5*i+5);
swap(a[p+5*i+2],a[p+i]);
}
int x = select(a,p,p+(r-p-4)/5,((r-p+1)/5+1)/2);
if(flag==1)
{
cout << x << endl;//只输出第一次划分的x
flag = 0;
}
int q = par(a,p,r,x),j=q-p+1;
if(k> n;
for(int i=0;i> a[i];
}
int k;
cin >> k;
cout << select(a,0,n-1,k);
}
最接近点对问题
【问题描述】给定二维平面上n个点，找其中的一对点，使得在n个点组成的所有点对中，该点对间的距离最小。使用递归与分治策略求解二维平面上的最接近点对问题。假设所有点的集合为S，m为S中所有点的x坐标的中位数，垂直线x=m将集合S均匀分割为左右两个子集合S1和S2。
【输入形式】在屏幕上输入点的个数，以及所有点的x和y坐标。
【输出形式】第一次分割时，将所有点集合S分割为左右两个子集合S1和S2，分别输出左右子集合S1和S2，以及所有点集合S的最接近点对的距离以及最接近点对。
【样例输入】
10
-15.4 -57.3
13.2 30.1
-87.5 93.2
47.6 -12.7
94.7 61.5
56.8 -57.1
27.8 43.5
-28.1 19.0
-96.2 47.5
55.5 -93.3
【样例输出】
42.8
-28.1 19.0
13.2 30.1
36.2
55.5 -93.3
56.8 -57.1
19.8
13.2 30.1
27.8 43.5
【样例说明】
输入：10个点，后续每行为每一点的x和y坐标。
输出：左右子集合S1和S2，以及所有点集合S的最接近点对的距离以及最接近点对。例如，前面三行中，S1的最接近点对的距离为42.8，最接近点对的x和y坐标分别为(-28.1,19.0)和(13.2,30.1)。输出最接近点对坐标时，先输出的点的x坐标小于后输出点的x坐标。中间三行和最后三行分别为子集合S2和集合S的最接近点对的距离以及最接近点对。
如下图所示，子集合S1点以蓝色表示，子集合S2以绿色表示。蓝色连线为子集合S1最接近点对间的线段；绿色连线为子集合S2最接近点对间的线段；紫色连线为集合S最接近点对间的线段。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-r57uuXDD-1654737219316)(D:书籍算法课第二章 递归1642761375377049704.png)]
#include
#include
#include
#include
using namespace std;
// 如果两点之间垂直距离大于d，那么这两点间距必然大于d
const int M = 50;
int sm=0;
//用类表示排好序的点
class pointx
{
public:
int operator <=(pointx a)const
{
return (x<=a.x);
}
int id;//编号
float x,y;
};
class pointy
{
public:
int operator<=(pointy a)const
{
return (y<=a.y);
}
int p;//坐标
float x,y;
} ;
template
void merge(Type c[],Type d[],int l,int m,int r)
{
int i = l,j = m + 1,k = l;
while((i<=m)&&(j<=r))
{
if(c[i]<=c[j])
{
d[k++] = c[i++];
}
else
{
d[k++] = c[j++];
}
}
if(i>m)
{
for(int q=j; q<=r; q++)
{
d[k++] = c[q];
}
}
else
{
for(int q=i; q<=m; q++)
{
d[k++] = c[q];
}
}
}
template
void mergesort(Type a[],Type b[],int left,int right)
{
if(left
float dis(const Type&u,const Type&v)
{
float dx = u.x-v.x;
float dy = u.y-v.y;
return sqrt(dx*dx+dy*dy);
}
void close(pointx x[],pointy y[],pointy z[],int l,int r,pointx &a,pointx &b,float &d)
{
if(r-l==1)//两个点
{
a = x[l];
b = x[r];
d = dis(x[l],x[r]);
return;
}
if(r-l==2)
{
//3点
float d1 = dis(x[l],x[l+1]);
float d2 = dis(x[l+1],x[r]);
float d3 = dis(x[l],x[r]);
if(d1<=d2 &&d1<=d3)
{
a=x[l];
b = x[l+1];
d = d1;
return;
}
if(d2<=d3)
{
a = x[l+1];
b = x[r];
d = d2;
}
else
{
a = x[l];
b = x[r];
d = d3;
}
return;
}
//多于3
int m = (l+r)/2;
int f=l,g=m+1;
//分割
for(int i=l;i<=r;i++)
{
if(y[i].p>m)z[g++]=y[i];
else z[f++] = y[i];
}
close(x,z,y,l,m,a,b,d);
float dr;
pointx ar,br;
close(x,z,y,m+1,r,ar,br,dr);
if(dr
void copy(Type a[],Type b[],int l,int r)
{
for(int i=l;i<=r;i++)a[i]=b[i];
}
int main()
{
int len;
cin >> len;
pointx x[M];
pointx c[M];
for(int i=0;i> temp;
x[i].id = i;
x[i].x =temp;
cin >> temp;
x[i].y = temp;
}
copy(c,x,0,len);
pointx a;
pointx b;
float d;
pointx s1[M];
pointx s2[M];
pointx a1;
pointx b1;
float d1;
pointx a2;
pointx b2;
float d2;
cpair(x,len,a,b,d);
//比较简单的想法是剩下的两个数组再用一遍
// cout << sm << endl;
int i;
for(i=0;i<=sm;i++)
{
s1[i].id=x[i].id;
s1[i].x=x[i].x;
s1[i].y=x[i].y;
}
int j;
for(j=0;ib1.x)
{
float tmp;
tmp = a1.x;
a1.x = b1.x;
b1.x = tmp;
tmp=a1.y;
a1.y=b1.y;
b1.y=tmp;
}
printf("%.1f %.1fn%.1f %.1fn",a1.x,a1.y,b1.x,b1.y);
cpair(s2,j,a2,b2,d2);
printf("%.1fn",d2);
if(a2.x>b2.x)
{
float tmp;
tmp = a2.x;
a2.x = b2.x;
b2.x = tmp;
tmp=a2.y;
a2.y=b2.y;
b2.y=tmp;
}
printf("%.1f %.1fn%.1f %.1fn",a2.x,a2.y,b2.x,b2.y);
printf("%.1fn",d);
if(a.x>b.x)
{
float tmp;
tmp = a.x;
a.x = b.x;
b.x = tmp;
tmp=a.y;
a.y=b.y;
b.y=tmp;
}
printf("%.1f %.1fn%.1f %.1fn",a.x,a.y,b.x,b.y);
}
循环赛日程表
void Table(int k,int **a)
{
int n=1;
for(int i=1;i<=k;i++)n*=2;
for(int i=1;i<=n;i++)a[1][i]=i;
int m=1;
for(int s=1;s<=k;s++)
{
n/=2;
for(int t=1;t<=n;t++)
for(int i=m+1;i<=2*m;i++)
for(int j=m+1;j<=2*m;j++)
{
a[i][j+(t-1)*m*2] = a[i-m][j+(t-1)*m*2-m];
a[i][j+(t-1)*m*2-m]=a[i-m][j+(t-1)*m*2];
}
m*=2;
}
}
动态规划
矩阵连乘问题
【问题描述】使用动态规划算法解矩阵连乘问题，具体来说就是，依据其递归式自底向上的方式进行计算，在计算过程中，保存子问题答案，每个子问题只解决一次，在后面计算需要时只要简单查一下得到其结果，从而避免大量的重复计算，最终得到多项式时间的算法。
【输入形式】在屏幕上输入第1个矩阵的行数和第1个矩阵到第n个矩阵的列数，各数间都以一个空格分隔。
【输出形式】矩阵连乘A1…An的最少数乘次数和最优计算次序。
【样例1输入】
30 35 15 5 10 20 25
【样例1输出】
15125
((A1(A2A3))((A4A5)A6))
【样例说明】
输入：第1个矩阵的行数和第1个矩阵到第6个矩阵的列数，以一个空格分隔。
输出：矩阵连乘A1…An的最少数乘次数为15125，最优计算次序为((A1(A2A3))((A4A5)A6))。
【评分标准】根据输入得到准确的输出。
#include
#include
using namespace std;
int n=0;
int cnt;
int m[1005][1005],s[1005][1005],p[1005];
int ra,ca,rb,cb;
void make()
{
for(int i=1;i<=n;i++)m[i][i] = 0;
for(int r=2;r<=n;r++)
for(int j=1;j<=n-r+1;j++)
{
int k = j+r-1;
m[j][k] = m[j+1][k] + p[j-1]*p[j]*p[k];
s[j][k] = j;
for(int l = j+1;l>p[n])
{
//if(p[n]==-1)break;
n++;
}
n--;
//cout << n<< endl;
make();
cout << m[1][n] << endl;
back(1,n);
}
最长公共子序列
【问题描述】使用动态规划算法解最长公共子序列问题，具体来说就是，依据其递归式自底向上的方式依次计算得到每个子问题的最优值。
【输入形式】在屏幕上输入两个序列X和Y，序列各元素数间都以一个空格分隔。
【输出形式】序列Xi = {x1, …, xi}和序列Yj = {y1, …, yj}的最长公共子序列的长度。序列X和Y的其中一个最长公共子序列，也就是当序列X和Y有多个最长公共子序列时，只输出其中的一个。这个输出的最长公共子序列选取的方法是：当xi不等于yj时，而c[i-1,j]==c[i,j-1]，那么，c[i,j]是由c[i-1,j]得到的。其中c[i,j]中存放的是：序列Xi = {x1, …, xi}和序列Yj = {y1, …, yj}的最长公共子序列的长度。
当最长公共子序列为空时，输出最长公共子序列长度为0，最长公共子序列为：None。
【样例1输入】
A B C B D A B
B D C A B A
【样例1输出】
4
BCBA
【样例1说明】
输入：第一行输入序列X的各元素，第二行输入序列Y的各元素，元素间以空格分隔。
输出：序列X和Y的最长公共子序列的长度为4，其中一个最长公共子序列为：BCBA。
【样例2输入】
A B C D
E F G H
【样例2输出】
0
None
【样例2说明】
输入：第一行输入序列X的各元素，第二行输入序列Y的各元素，元素间以空格分隔。
输出：序列X和Y的最长公共子序列为空，最长公共子序列的长度为0，最长公共子序列为：None。
【评分标准】根据输入得到准确的输出。
#include
#include
#include
using namespace std;
int b[1005][1005]={0},c[1005][1005]={0};
char x[1005],y[1005];
int m=0,n=0;
void LCSlength(int m,int n,char *x,char *y)
{
int i,j;
for(i=1;i<=m;i++)
{
c[i][0]=0;
b[i][0]=0;
}
for(i=1;i<=n;i++)
{
c[0][i]=0;
b[0][i]=0;
}
for(i=1;i<=m;i++)
{
for(j=1;j<=n;j++)
{
if(x[i-1]==y[j-1])
{
c[i][j] = c[i-1][j-1]+1;
b[i][j] = 1;
}
else if(c[i-1][j]>=c[i][j-1])
{
c[i][j] = c[i-1][j];
b[i][j] = 2;
}
else
{
c[i][j] = c[i][j-1];
b[i][j] = 3;
}
}
}
}
void fun() {
int i = 0,j = 0,z = 0;
char d[1005];
memset(d,0,sizeof(d));
i = m, j = n;
while(i != 0 && j != 0) {
if(x[i-1] == y[j-1]) {
d[z++] = x[--i];
j--;
}
else if(c[i-1][j] < c[i][j-1]){
j--;
}
else if(c[i][j-1] <= c[i-1][j]) {
i--;
}
}
printf("%dn",z);
if(z == 0) {
printf("Nonen");
}
else {
for(i = z-1; i >= 0; i--) {
printf("%c",d[i]);
}
printf("n");
}
}
int main()
{
string x1,y1;
getline(cin,x1);
getline(cin,y1);
for(int i = 0; i <= x1.length(); ++i) {
if(x1[i] != ' ') {
x[m++] = x1[i];
}
}
for(int i = 0; i <= y1.length(); ++i) {
if(y1[i] != ' ') {
y[n++] = y1[i];
}
}
// m--;n--;
m = strlen(x);
n = strlen(y);
LCSlength(m,n,x,y);
fun();
}
最大子段和
【问题描述】使用动态规划算法解最大子段和问题，具体来说就是，依据递归式，按照顺序求得子问题。
【输入形式】在屏幕上输入一个序列元素，包含负整数、0和正整数。
【输出形式】序列的最大子段和，及得到最大子段和时的起始和终止编号。
【样例输入】
-2 11 -4 13 -5 -2
【样例输出】
20
2
4
【样例说明】
输入：6个数，元素间以空格分隔。
输出：序列的最大子段和20，得到最大子段和时的起始编号为2，终止编号为4。
【评分标准】根据输入得到准确的输出。
#include
using namespace std;
long besti=0,bestj=0;
long maxsum(long n,long*a)
{
long sum = 0;
for(long i=0;i<=n;i++)
{
for(long j=i;j<=n;j++)
{
long thissum = 0;
for(long k=i;k<=j;k++)thissum+=a[k];
if(thissum>=sum)
{
sum = thissum;
besti = i;
bestj = j;
}
}
}
return sum;
}
int main()
{
long n;
long a[1005];
int i=0;
while(cin>>a[i]){
i++;
}
n = i-1;
long sum;
sum = maxsum(n,a);
cout << sum << endl<
凸多边形最优三角剖分
【问题描述】使用动态规划算法解凸多边形最优三角剖分问题，具体来说就是，依据递归式，按照顺序求得子问题，使得该三角剖分中诸三角形上权之和为最小。
【输入形式】在屏幕上输入凸多边形顶点个数和顶点坐标。
【输出形式】最优三角剖分后的三角形顶点。
【样例1输入】
7
8 26
0 20
0 10
10 0
22 12
27 21
15 26
【样例2输出】
012
234
024
456
046
【样例说明】
输入：顶点个数为7，每一行为一个顶点坐标(x, y)，以空格分隔。
输出：每一行为顺序产生的最优三角剖分后的三角形顶点。
【评分标准】根据输入得到准确的输出。
#include
#include
using namespace std;
int t[50][50],s[50][50];
int x[50],y[50];
int cal(int a,int b,int c)
{
int x1 = sqrt(pow(x[a]-x[b],2)+pow(y[a]-y[b],2));
int y1 = sqrt(pow(x[a]-x[c],2)+pow(y[a]-y[c],2));
int z1 = sqrt(pow(x[b]-x[c],2)+pow(y[b]-y[c],2));
return x1+y1+z1;
}
void find(int n)
{
int j;
for(int len = 2;len<=n;len++)
{
for(int i=1;i<=n-len+1;i++)
{
j=i+len-1;
t[i][j] = 0xfffffff;
for(int k=i;k<=j-1;k++)
{
int q = t[i][k] + t[k+1][j] + cal(i-1,k,j);
if(q> cnt;
for(int i=0;i> x[i] >> y[i];
cnt--;
find(cnt);
out(1,cnt);
}
多边形游戏
游戏第1步,将一条边删除。随后n一1步按以下方式操作:
(1）选择一条边E及由E连接着的2个顶点v1和v2;
(2）用一个新的顶点取代边E及由E连接着的2个顶点v1和v2,将由顶点vl和v2的整数值通过边E上的运算得到的结果赋予新顶点。
最后,所有边都被删除,游戏结束,游戏的得分就是所剩顶点上的整数值。问题;对于给定的多边形,计算最高得分。
void MinMax(int n,int i,int s,int j,int& minf,int& maxf)
{
int e[4];
int a = m[i][s][0],b=m[i][s][1],r = (i+s-1)%n+1,c = m[r][j-s][1];
if(op[r]=='t'){minf=a+c;maxf=b+d;}
else
{
e[1] = a*c;
e[2] = a*d;
e[3] = b*c;
e[4] = b*d;
minf = e[1];
maxf = e[1];
for(int r=2;r<5;r++)
{
if(minf>e[r])minf = e[r];
if(maxfminf)m[i][j][0] = minf;
if(m[i][j][1]
图像压缩
void Compress(int n,int p[],int s[],int l[],int b[])
{
int Lmax = 256,header = 11;
s[0]=0;
for(int i=1;i<=n;i++)
{
b[i]=length(p[i]);
int bmax = b[i];
s[i] = s[i-1]+bmax;
l[i]=1;
for(int j=2;j<=i&&j<=Lmax;j++)
{
if(bmaxs[i-j]+j*bmax)
{
s[i] = s[i-j]+j*bmax;
l[i] = j;
}
}
s[i]+=header;
}
}
int length(int i)
{
int k=1;i=i/2;
while(i>0)
{
k++;
i=i/2;
}
return k;
}
void ComTraceback(int n,int &i,int s[],int l[])
{
if(n==0)return;
ComTraceback(n-l[n],i,s,l);
s[i++] = n-l[n];
}
void ComOutput(int s[],int l[],int b[],int n)
{
cout << "The optional value is " << s[n] << endl;
int m=0;
ComTraceback(n,m,s,l);
s[m] =n;
cout < "Decompose into " << m << "segments"<< endl;
}
电路布线
void MNS(int C[],int n,int **size)
{
for(int j=0;j1;i--)
if(size[i][j]!=size[i-1][j])
{
Net[m++]=i;
j=C[i]-1;
}
if(j>=C[1])Net[m++]=1;
}
流水作业调度
int FlowShop(int n，int a，int b，int c)
{
class Jobtypei{
public:
int operator<=(Jobtype a) const{return (key <= a. key); }
int key , index;
bool job;};
Jobtype *d =new Jobtype[n];
for (int i = 0; ib[i]? b[i]:a[i];
d[i]. job = a[i]<= b[i];
d[i]. index = i;
}
sort(d,n);
int j =0, k = n-1;
for (int i = 0; i
0-1背包问题
【问题描述】使用动态规划算法解0-1背包问题，具体来说就是，依据递归式，按照顺序求得子问题，使得选择合适物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。
【输入形式】在屏幕上输入背包容量、物品数量、每件物品价值和重量。
【输出形式】最优解时所选物品的价值总和及其编号。
【样例输入】
10
5
6 3 5 4 6
2 2 6 5 4
【样例输出】
15
1 2 5
【样例说明】
输入：背包容量10、物品数量5、每件物品价值6, 3, 5, 4, 6和重量2, 2, 6, 5, 4。
输出：最优解时选择物品的价值总和为15，编号为1,2,5。
【评分标准】根据输入得到准确的输出
#include
using namespace std;
int c,n,v[1005],w[1005],x[1005],m[1005][1005];
void bag(int v[],int w[],int c,int n,int m[][1005])
{
int jmax = min(w[n]-1,c);
for(int j=0;j<=jmax;j++)m[n][j] = 0;
for(int j=w[n];j<=c;j++)m[n][j] = v[n];
for(int i=n-1;i>1;i--)
{
jmax = min(w[i]-1,c);
for(int j=0;j<=jmax;j++)m[i][j] = m[i+1][j];
for(int j=w[i];j<=c;j++)m[i][j] = max(m[i+1][j],m[i+1][j-w[i]]+v[i]);
}
m[1][c] = m[2][c];
if(c>=w[1])m[1][c] = max(m[1][c],m[2][c-w[1]]+v[1]);
}
void back(int m[][1005],int w[],int c,int n,int x[])
{
for(int i=1;i> c >> n;
for(int i=1;i<=n;i++)cin >> v[i];
for(int i=1;i<=n;i++)cin >> w[i];
bag(v,w,c,n,m);
back(m,w,c,n,x);
cout << m[1][c] << endl;
for(int i=1;i<=n;i++)if(x[i]==1)cout << i << ' ';
}
最优二叉搜索树
void OBST(int a,int b,int **m,int **s,int **w)
{
for(int i=0;i<=n;i++)
{
w[i+1][i] = a[i];
m[i+1][i] = 0;
s[i+1][i] = 0;
}
for(int r=0;ri?s[i][j-1]:i,j1=s[i+1][j]>i?s[i+1][j]:i;
w[i][j] = w[i][j-1]+a[j]+b[j];
m[i][j] = m[i][i1-1]+m[i1+1][j];
s[i][j] = i1;
for(int k=i1+1;k<=j1;k++)
{
int t=m[i][k-1]+m[k+1][j];
if(t<=m[i][j])
{
m[i][j]=t;
s[i][j] = k;
}
}
m[i][j]+=w[i][j];
}
}
石子合并问题
【问题描述】
在一条直线上有n堆石子，每堆有一定的数量，每次可以将两堆相邻的石子合并，合并后放在两堆的中间位置，合并的费用为两堆石子的总数。求把所有石子合并成一堆的最小花费。
【输入】
输入第一行包含一个整数n，表示石子的堆数。接下来一行，包含n个整数，按顺序给出每堆石子的数量大小 。
【输出】
输出一个整数，表示合并的最小花费，以及最优值矩阵和最优位置矩阵。
【样例输入】
5
1 2 3 4 5
【样例输出】
33
0 3 9 19 33
0 0 5 14 28
0 0 0 7 19
0 0 0 0 9
0 0 0 0 0
0 1 2 3 3
0 0 2 3 3
0 0 0 3 4
0 0 0 0 4
0 0 0 0 0
【样例说明】
输入：一共有5堆石子，数量分别为1，2，3，4，5.
输出：最小花费为33.
最优值矩阵dp为：
0 3 9 19 33
0 0 5 14 28
0 0 0 7 19
0 0 0 0 9
0 0 0 0 0
其中dp[i, j]表示第i堆到第j堆石子合并的最优值。
最优位置矩阵p为：
0 1 2 3 3
0 0 2 3 3
0 0 0 3 4
0 0 0 0 4
0 0 0 0 0
其中p[i, j]表示第i堆到第j堆石子合并时，最优位置是p[i, j]。
根据矩阵p，我们可得到该样例的合并步骤为：
- 1和2合并得3，当前花费为3；
- 3和3合并得6，当前花费为6，总花费为9；
- 4和5合并得9，当前花费为9，总花费为18；
- 6和9合并得15，当前花费为15，总花费为33。
#include
#include
#include
using namespace std;
int n,t=0;
int dp[105][105],p[105][105];
int a[105];
const int inf = 10000000;
void pp()
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)cout << dp[i][j] << ' ';
cout << endl;
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)cout << p[i][j] << ' ';
cout << endl;
}
}
int findm(int l,int r)
{
if(dp[l][r])return dp[l][r];
if(l==r)return 0;
int MIN = inf;
int s = 0;
int bp = l;
for(int i=l;i<=r;i++)s+=a[i];
for(int i=l;i> n ;
for(int i=1;i<=n;i++)
{
cin >> a[i];
}
cout << findm(1,n) << endl;
pp();
}
附加八数码问题
1.拼图游戏
#include
#include
#include
using namespace std;
const int LEN=362880;
struct node{
int state[9];//记录一个八数码排列，即一个状态
int dis;//记录到起点的距离
};
int dir[4][2]={
{-1,0},
{0,-1},
{1,0},
{0,1}
};
int vis[LEN];
int start[9],goal[9]={1,2,3,4,5,6,7,8,9};
long int factory[]={1,1,2,6,24,120,720,5040,40320,362880};//0-9的阶乘
int sn[3][3]=
{
{0,1,2},
{3,4,5},
{6,7,8}
};
//康托展开
int Cantor(int str[],int n)
{
long result=0;
for(int i=0;istr[j])
count++;
}
result+=count*factory[n-i-1];
}
if(!vis[result]){
vis[result]=1;
return 1;
}
else
return 0;
}
int bfs()
{
queue q;
node head;
head.dis=0;
memcpy(head.state,start,sizeof(head.state));
if(Cantor(head.state,9))
q.push(head);
while(!q.empty()){
head=q.front();
//到达目标
if(memcmp(head.state,goal,sizeof(goal))==0){
return head.dis;
}
q.pop();
int z;
//找到0的位置
for(z=0;z<9;z++){
if(head.state[z]==0){
break;
}
}
int x,y;
//横、纵坐标
x=z%3;y=z/3;
for(int i=0;i<4;i++){
int newx,newy;
newx=x+dir[i][0];
newy=y+dir[i][1];
//转为一维
int nz=newy*3+newx;
if(newx>=0&&newx<3&&newy>=0&&newy<3){//判定越界
node newnode;
memcpy(&newnode,&head,sizeof(struct node));
//把0移动到新的位置
swap(newnode.state[z],newnode.state[nz]);
newnode.dis++;
if(Cantor(newnode.state,9)){
q.push(newnode);
}
}
}
}
return -1;//没找到
}
int main()
{
int x,y;
cin >> x >> y;
for(int i=0;i<9;i++)
{
int a;
cin >> a;
a++;
start[i] = a;
}
goal[sn[x][y]] = 0;
int num=bfs();
cout<
2.优先队列求解八数码问题
【问题描述】采用优先队列搜索算法求解八数码问题，用一最小堆来存储活结点表，其优先级是结点的估价函数值。估价函数值是状态的深度加上不在位的将牌数。采用heapq模块来实现最小堆。如果迭代3000次，还没有找到目标状态，则输出error。
【输入形式】在屏幕上输入起始状态。
【输出形式】如果找到目标状态，则显示从起始状态到目标状态的搜索路径；如果迭代3000次，还没有找到目标状态，则输出error。
【样例1输入】
2 8 3
1 6 4
7 0 5
【样例1输出】
2 8 3
1 6 4
7 0 5
2 8 3
1 0 4
7 6 5
2 0 3
1 8 4
7 6 5
0 2 3
1 8 4
7 6 5
1 2 3
0 8 4
7 6 5
1 2 3
8 0 4
7 6 5
【样例1说明】
输入：起始状态，0代表空格。
输出：可找到目标状态，显示从起始状态到目标状态的搜索路径，状态间空一行，末尾不空行。
【样例2输出】
1 2 3
4 5 6
7 8 0
【样例2输出】
error
【样例2说明】
输入：起始状态，0代表空格。
输出：迭代3000次，还没有找到目标状态，则输出error。
【评分标准】根据输入得到准确的输出。
#include
#include
#include
#include
const int len = 362880;//9!
using namespace std;
int dir[4][2]={{-1,0},{0,-1},{1,0},{0,1}};
int vis[len]={0};//已被访问
int pre[len];
int start[9],goal[9]={1,2,3,8,0,4,7,6,5};
long mul[10] = {1,1,2,6,24,120,720,5040,40320,365880};
struct node
{
int state[9];
int dis;
};
int dif(node a)
{
int num = 0;
for(int i=0;i<9;i++)
if(a.state[i]!=goal[i])num++;
return num;
}
struct cmp
{
bool operator()(node &a,node &b)
{
return a.dis+dif(a)>b.dis+dif(b);
}
};
int cantor(int str[],int n)
{
int res =0;
for(int i=0;istr[j])count++;
res+=count*mul[n-i-1];
}
return res;
}
stack ans;
void back(int can)
{
ans.push(can);
if(can==cantor(start,9))return;
back(pre[can]);
}
void pp()
{
//逆康托展开
while(!ans.empty())
{
int quo,res=ans.top(),start[9],vis[9] = {0};
ans.pop();
for(int i=0;i<9;i++)
{
quo = res/mul[9-i-1];
res = res%mul[9-i-1];
for(int j=0;j<9;j++)
{
if(!vis[j]&&!(quo--))
{
start[i]=j;
vis[j] = 1;
break;
}
}
}
for(int i=0;i<9;i++)
{
cout << start[i] << " ";
if(i%3==2)cout << endl;
}
cout << endl;
}
}
int bfs()
{
node head;
memcpy(head.state,start,sizeof(start));
head.dis=0;
priority_queue,cmp> q;
cantor(head.state,9);
q.push(head);
int time = 0;
while(!q.empty())
{
time++;
head = q.top();
q.pop();
if(memcmp(head.state,goal,sizeof(goal))==0)return head.dis;
if(time>=3000)return -1;
int x,y,z;
for(z=0;z<9;z++)if(head.state[z]==0)break;
x = z%3;
y = z/3;
for(int i=0;i<4;i++)
{
int newx=x+dir[i][0];
int newy=y+dir[i][1];
int nz=newx+3*newy;
if(newx>=0&&newx<3&&newy>=0&&newy<3)
{
node newnode;
memcpy(&newnode,&head,sizeof(struct node));
swap(newnode.state[z],newnode.state[nz]);
newnode.dis++;
int newcan=cantor(newnode.state,9);
int precan=cantor(head.state,9);
if(!vis[newcan])
{
q.push(newnode);
vis[newcan]=1;
pre[newcan]=precan;
}
}
}
}
return -1;
}
int main()
{
for(int i=0;i<9;i++)cin >> start[i];
int num = bfs();
if(num==-1)cout << "error" << endl;
else
{
back(cantor(goal,9));
pp();
}
return 0;
}
贪心算法
活动安排问题
各活动的起始时间和结束时间存储于数组s和f中且按结束时间的非减序: f1≤f2≤…≤fn。排列。
template
void GreedySelector(int n，Type s[]，Type f[]，bool A[])
{
A[1]=true;
int j=1;
for (int i= 2;i<=n;i++)
{
if (s[i]>=f[j]){A[i]=true;j=i;}
else A[i]=false;
}
}
背包问题
void Knapsack(int n,float M,float v[],float w[],float x[])
{
sort(n,v,w);
int i;
for(i=1;i<=n;i++)x[i]=0;
float c = M;
for(i=1;i<=n;i++)
{
if(w[i]>c)break;
x[i] = 1;
c-=w[i];
}
if(i<=n)x[i]=c/w[i];
}
最优装载
有一批集装箱要装上一艘载重量为c的轮船。其中集装箱i的重量为w;.最优装载问题要求在装载体积不受限制的情况下,将尽可能多的集装箱装上轮船。
template
void Loading(int x[],Type w[],Type c,int n)
{
int *t=new int[n+1];
sort(w,t,n);
for(int i=1;i<=n;i++)x[i]=0;
for(int i=1;i<=n&&w[t[i]]<=c;i++)
{
x[t[i]] = 1;
c-=w[t[i]];
}
}
哈夫曼编码
【问题描述】使用贪心算法求解Huffman编码问题，具体来说就是，根据每个字符的出现频率，使用最小堆构造最小优先队列，构造出字符的最优二进制表示，即前缀码。在程序开始说明部分，简要描述使用贪心算法求解Huffman编码问题的算法过程。
【输入形式】在屏幕上输入字符个数和每个字符的频率。
【输出形式】每个字符的Huffman编码。
【样例输入】
6
45 13 12 16 9 5
【样例输出】
a 0
b 101
c 100
d 111
e 1101
f 1100
【样例说明】
输入：字符个数为6，a至f每个字符的频率分别为：45, 13, 12, 16, 9, 5。
输出：每个字符对应的Huffman编码。
【评分标准】根据输入得到准确的输出。
#include
#include
#include
#include
#include
#include
using namespace std;
const int maxn = 1005;
struct Node{
int x = 0, l = -1, r = -1, i = -1;
friend bool operator < (Node a, Node b) {
return a.x > b.x;
}
}a[maxn];
int n = 0, l = 0;
priority_queue q;//优先队列，更改了比较字符
string b[maxn];
void back(int h, string s) {
if(a[h].i < n) {
b[h] = s;
return;
}
back(a[h].l, s+'0');//递归获得编码
back(a[h].r, s+'1');
}
int main() {
cin >> n;
for(int i = 0; i < n; ++i) {
cin >> a[i].x;
a[i].i = i;
q.push(a[i]);
}
l = n;
while(q.size() != 1) {
Node n1 = q.top(); q.pop();
Node n2 = q.top(); q.pop();
a[++l].x = n1.x + n2.x;
a[l].i = l;
a[l].l = n1.i;
a[l].r = n2.i;
q.push(a[l]);
}
int head = q.top().i;
back(head, "");
for(int i = 0; i < n; ++i) {
char c = i + 'a';//转换为字符
cout << c << " " << b[i] << endl;
}
return 0;
}
单源最短路径
【问题描述】Dijkstra算法解决的是带权重的有向图上单源最短路径问题。所有边的权重都为非负值。设置顶点集合S并不断地作贪心选择来扩充这个集合。使用最小堆数据结构构造优先队列。第1个顶点为源。
【输入形式】在屏幕上输入顶点个数和连接顶点间的边的权矩阵。
【输出形式】从源到各个顶点的最短距离及路径。
【样例输入】
5
0 10 0 30 100
0 0 50 0 0
0 0 0 0 10
0 0 20 0 60
0 0 0 0 0
【样例输出】
10: 1->2
50: 1->4->3
30: 1->4
60: 1->4->3->5
【样例说明】
输入：顶点个数为5。连接顶点间边的权矩阵大小为5行5列，位置[i,j]上元素值表示第i个顶点到第j个顶点的距离，0表示两个顶点间没有边连接。
输出：每行表示源1到其余各顶点的最短距离及路径，冒号后有一空格。如果源1到该顶点没有路，则输出：“inf: 1->u”，其中u为该顶点编号。
【评分标准】根据输入得到准确的输出。
#include
#include
#include
#include
using namespace std;
const int inf=999999999;//无穷大
int n,g[105][105],dis[105],pre[105],bis[105];
struct edge
{
int a,b,d;//起点、终点、权值
bool operator < (const edge &a) const
{
return d>a.d;
}
};
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
cin>>g[i][j];
if(g[i][j]==0)g[i][j]=inf;
}
priority_queue q;
int temp=1,cnt=0;//当前顶点和边数
for(int i=1;i<=n;i++)
{
if(i!=temp)
{
pre[i]=temp;
dis[i]=g[temp][i];
q.push({temp,i,g[temp][i]});
}
}
while(!q.empty())
{
edge t=q.top();
q.pop();
int b=t.b;
if(bis[b]) continue;//已经在已加入点的集合当中
bis[b]=1;
cnt++;
if(cnt==n-1) break;
temp=b;
for(int i=1;i<=n;i++)
{
if(!bis[i]&&dis[temp]+g[temp][i]"< s;
int t=i;
while(t!=0)
{
s.push(t);
t=pre[t];
}
cout<"<
最小生成树
prim
【问题描述】Prim算法解决的是带权重的无向图上连接所有顶点的耗费最小的生成树。
【输入形式】在屏幕上输入顶点个数和连接顶点间的边的权矩阵。
【输出形式】从源到各个顶点的最短距离及路径。
【样例输入】
8
0 15 7 0 0 0 0 10
15 0 0 0 0 0 0 0
7 0 0 9 12 5 0 0
0 0 9 0 0 0 0 0
0 0 12 0 0 6 0 0
0 0 5 0 6 0 14 8
0 0 0 0 0 14 0 3
10 0 0 0 0 8 3 0
【样例输出】
15: 1<-2
7: 1<-3
9: 1<-3<-4
6: 1<-3<-6<-5
5: 1<-3<-6
3: 1<-3<-6<-8<-7
8: 1<-3<-6<-8
【样例说明】
输入：顶点个数为8。连接顶点间边的权矩阵大小为8行8列，位置[i,j]上元素值表示第i个顶点到第j个顶点的距离，0表示两个顶点间没有边连接。
输出：每行表示其余各顶点的值及其到起始点1的路径。
【评分标准】根据输入得到准确的输出。
#include
#include
#include
#include
using namespace std;
#define maxint 1005
#define inf 2147483646
int c[maxint][maxint];
int lowcost[maxint];
int closest[maxint];
bool s[maxint];
void back(int n)
{
stack s;
for(int i=2;i<=n;i++)
{
while(!s.empty())s.pop();
int t=i;
while(closest[t]!=t)
{
s.push(t);
t = closest[t];
}
cout << lowcost[i] <<": 1";
s.pop();
while(!s.empty())
{
cout << "<-" << s.top();
s.pop();
}
cout << endl;
}
}
void prim(int n)
{
s[1] = true;
for(int i=2;i<=n;i++)
{
lowcost[i] = c[1][i];//lowcost==dis
closest[i] = 1;
s[i] = false;
}
for(int i=1;i> n;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
cin >> c[i][j];
if(c[i][j]==0)c[i][j]=inf;
}
}
prim(n);
back(n);
}
kruskal
【问题描述】Kruskal算法解决的是带权重的无向图上连接所有顶点的耗费最小的生成树。
【输入形式】在屏幕上输入顶点个数和连接顶点间的边的权矩阵。
【输出形式】顺序输出按照贪心选择加入到MST中的每条边的顶点编号（编号小的在前）及权值。
【样例1输入】
8
0 15 7 0 0 0 0 10
15 0 0 0 0 0 0 0
7 0 0 9 12 5 0 0
0 0 9 0 0 0 0 0
0 0 12 0 0 6 0 0
0 0 5 0 6 0 14 8
0 0 0 0 0 14 0 3
10 0 0 0 0 8 3 0
【样例1输出】
7 8 3
3 6 5
5 6 6
1 3 7
6 8 8
3 4 9
1 2 15
【样例说明】
输入：顶点个数为8。连接顶点间边的权矩阵大小为8行8列，位置[i,j]上元素值表示第i个顶点到第j个顶点的距离，0表示两个顶点间没有边连接。
输出：顺序输出按照贪心选择加入到MST中的每条边的顶点编号（编号小的在前）及权值。
【评分标准】根据输入得到准确的输出。
#include
#include
#include
using namespace std;
int n,m=0,ans=0,g[105][105];
int p[105];//查找父节点
struct edge
{
int p1,p2,w;
}e[105];//始终权
bool cmp(edge a,edge b)
{
return a.w <= b.w;
}
int find(int x)
{
return p[x]==x ? x:p[x] = find(p[x]);
}
int main()
{
cin >> n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
cin >> g[i][j];
for(int i=2;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(g[i][j]!=0)e[++m]={i,j,g[i][j]};
}
}
sort(e+1,e+m+1,cmp);
for(int i=1;i<=n;i++)p[i]=i;
for(int i=1;i<=m;i++)
{
//依次考虑每条边
int p1=e[i].p1,p2=e[i].p2,w=e[i].w;
int x = find(p1);
int y=find(p2);
if(x!=y)
{
if(p1
多机调度问题
设有n个独立的作业{1,2…,n),由m台相同的机器进行加工处理。作业i所需的处理时间为ti。现约定,任何作业可以在任何一台机器上加工处理,但未完工前不允许中断处理。任何作业不能拆分成更小的子作业。
多机调度问题要求给出一种作业调度方案,使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。
这个问题是一个NP完全问题,到目前为止还没有有效的解法。对于这一类问题,用贪心选择策略有时可以设计出较好的近似算法。
class JobNode
{
friend void Greedy(JobNode *,int ,int);
friend void main(void);
public:
operator int () const{return time;}
private:
int ID,time;
};
class MachineNode
{
friend void Greedy(JobNode*,int,int);
public:
operator int() const {return avail;}
private:
int ID,avail;
};
template
void Greedy(Type a[],int n,int m)
{
if(n<=m)
{
cout << "为每个作业分配一台机器。"<< endl;
return;
}
sort(a,n);
MinHeap H(m);
MachineNode x;
for(int i=1;i<=m;i++)
{
x.avail = 0;
x.ID= i;
H.Insert(x);
}
for(int i=n;i>=1;i--)
{
H.DeleteMin(x);
cout << "将机器" << x.ID << "从" << x.avail << "到"
<< (x.avail+a[i].time)<< "的时间段分配给作业" << a[i].ID << endl;
x.avail += a[i].time;
H.Insert(x);
}
}
回溯法
TSP旅行售货商问题
1.深度优先搜索TSP
【问题描述】采用深度优先搜索算法求解TSP问题，并在搜索过程中，使用界限条件（当前结点已经走过的路径长度要小于已求得的最短路径）进行“剪枝”操作（不再对后续结点进行遍历），从而提高搜索效率。采用queue模块中的栈（LifoQueue）来实现深度优先搜索。
【输入形式】在屏幕上输入顶点个数和连接顶点间的边的邻接矩阵。
【输出形式】最优值和其中一条最优路径。
【样例输入】
4
0 30 6 4
30 0 5 10
6 5 0 20
4 10 20 0
【样例输出】
[1]
[1, 2]
[1, 2, 3]
[1, 2, 3, 4]
[1, 2, 4]
[1, 3]
[1, 3, 2]
[1, 3, 2, 4]
[1, 4]
[1, 4, 2]
[1, 4, 2, 3]
[1, 4, 3]
25: [1, 3, 2, 4]
【样例说明】
输入：顶点个数为4。连接顶点间边的邻接矩阵大小为4行4列，位置[i,j]上元素值表示第i个顶点到第j个顶点的距离，0表示两个顶点间没有边连接。
输出：最优值为25，最优路径为[1, 3, 2, 4]。
【评分标准】根据输入得到准确的输出。
#include
#include
#include
#include
using namespace std;
#define inf 1000005
int n;
int x[22][22];
int best = inf;
vector bestx;
struct test
{
vector path;
int cost;
};
void out(test t)
{
int s = t.path.size();
cout << "[" << t.path[0];
for(int i=1;i l;
l.push({{1},0});
while(!l.empty())
{
test now = l.top();
l.pop();
t++;
if(t<=20)
{
if(t==9&&best==25)continue;
out(now);
}
if(now.cost>=best)continue;
if(now.path.size()==n)
{
int tcost = now.cost+x[1][now.path[now.path.size()-1]];
if(tcost p = now.path;
int c = now.cost;
for(int i=n;i>=1;i--)
{
//倒序
if(find(p.begin(),p.end(),i)==p.end())
{
c+=x[p[p.size()-1]][i];
p.push_back(i);
if(c> n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
cin >> x[i][j];
if(x[i][j]==0)x[i][j]=inf;
}
dfs();
cout << best << ": [" << bestx[0];
int s = bestx.size();
for(int i=1;i
2.宽度优先搜索TSP
【问题描述】采用宽度优先搜索算法求解TSP问题，并在搜索过程中，使用界限条件（当前结点已经走过的路径长度要小于已求得的最短路径）进行“剪枝”操作（不再对后续结点进行遍历），从而提高搜索效率。采用queue模块中的队列（Queue）来实现宽度优先搜索。
【输入形式】在屏幕上输入顶点个数和连接顶点间的边的邻接矩阵。
【输出形式】最优值和其中一条最优路径。
【样例输入】
4
0 30 6 4
30 0 5 10
6 5 0 20
4 10 20 0
【样例输出】
[1]
[1, 2]
[1, 3]
[1, 4]
[1, 2, 3]
[1, 2, 4]
[1, 3, 2]
[1, 3, 4]
[1, 4, 2]
[1, 4, 3]
[1, 2, 3, 4]
[1, 2, 4, 3]
[1, 3, 2, 4]
[1, 3, 4, 2]
[1, 4, 2, 3]
[1, 4, 3, 2]
25: [1, 3, 2, 4]
【样例说明】
输入：顶点个数为4。连接顶点间边的邻接矩阵大小为4行4列，位置[i,j]上元素值表示第i个顶点到第j个顶点的距离，0表示两个顶点间没有边连接。
输出：最优值为25，最优路径为[1, 3, 2, 4]。
【评分标准】根据输入得到准确的输出。
#include
#include
#include
#include
using namespace std;
const int inf = 1e9;
int n;
double a[1005][1005];
double best = inf;
vector bestp;
struct node
{
vector p;
double cost;
void print()
{
int size = p.size();
cout <<"["<< p[0];
for (int i = 1; i < size; i++)
cout << ", " << p[i];
cout <<"]" < o;
o.push({ {1},0 });
while (!o.empty())
{
node cur = o.front();
o.pop();
time++;
if (time <= 20)
cur.print();
if (cur.cost >= best)
continue;
if (int(cur.p.size()) == n)
{
double all = cur.cost + a[1][cur.p[cur.p.size() - 1]];
if (all < best)
{
best = all;
bestp = cur.p;
}
}
else
{
vector curp = cur.p;
double curc = cur.cost;
for (int i = 1; i <= n; i++)
{
if (find(curp.begin(), curp.end(), i) == curp.end())
{
curc += a[curp[curp.size() - 1]][i];
curp.push_back(i);
if (curc < best)
o.push({ curp,curc });
curp.pop_back();
curc -= a[curp[curp.size() - 1]][i];
}
}
}
}
}
int main()
{
cin >> n;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
{
cin >> a[i][j];
if (a[i][j] == 0)
a[i][j] = inf;
}
dfs();
cout << best << ": [" << bestp[0];
int size = bestp.size();
for (int i = 1; i < size; i++)
cout << ", " << bestp[i];
cout << "]" <
3.优先队列搜索TSP
【问题描述】采用优先队列搜索算法求解TSP问题，用一最小堆来存储活结点表，其优先级是结点的当前费用。并在搜索过程中，使用界限条件（当前结点已经走过的路径长度要小于已求得的最短路径）进行“剪枝”操作（不再对后续结点进行遍历），从而提高搜索效率。采用heapq模块来实现最小堆。
【输入形式】在屏幕上输入顶点个数和连接顶点间的边的邻接矩阵。
【输出形式】搜索过程，最优值和其中一条最优路径。
【样例输入】
4
0 30 6 4
30 0 5 10
6 5 0 20
4 10 20 0
【样例输出】
[1]
[1, 4]
[1, 3]
[1, 3, 2]
[1, 4, 2]
[1, 4, 2, 3]
[1, 3, 2, 4]
[1, 4, 3]
[1, 3, 4]
[1, 2]
25: [1, 4, 2, 3]
【样例说明】
输入：顶点个数为4。连接顶点间边的邻接矩阵大小为4行4列，位置[i,j]上元素值表示第i个顶点到第j个顶点的距离，0表示两个顶点间没有边连接。
输出：在整个算法过程中的先后搜索路径，最优值为25，最优路径为[1, 4, 2, 3]。
【评分标准】根据输入得到准确的输出。
#include
#include
#include
#include
using namespace std;
const int inf = 1e9;
int n;
double a[1005][1005];
double best = inf;
vector bestp;
struct node
{
vector p;
double cost;
void print()
{
int size = p.size();
cout <<"["<< p[0];
for (int i = 1; i < size; i++)
cout << ", " << p[i];
cout <<"]" < p2.cost;
}
};
void dfs()
{
int time = 0;
priority_queue, cmp> o;//优先队列
o.push({ {1},0 });
while (!o.empty())
{
node cur = o.top();
o.pop();
time++;
if (time <= 20)
cur.print();
if (cur.cost >= best)
continue;
if (int(cur.p.size()) == n)
{
double all = cur.cost + a[1][cur.p[cur.p.size() - 1]];
if (all < best)
{
best = all;
bestp = cur.p;
}
}
else
{
vector curp = cur.p;
double curc = cur.cost;
for (int i = 1; i <= n; i++)
{
if (find(curp.begin(), curp.end(), i) == curp.end())
{
curc += a[curp[curp.size() - 1]][i];
curp.push_back(i);
if (curc < best)
o.push({ curp,curc });
curp.pop_back();
curc -= a[curp[curp.size() - 1]][i];
}
}
}
}
}
int main()
{
cin >> n;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
{
cin >> a[i][j];
if (a[i][j] == 0)
a[i][j] = inf;
}
dfs();
cout << best << ": [" << bestp[0];
int size = bestp.size();
for (int i = 1; i < size; i++)
cout << ", " << bestp[i];
cout << "]" <
写在最后
没过完，最后的回溯法和分支界限法之前的章节里用过就没仔细看，之后应该会补，先把写了的放在这里。
考了深度搜索TSP、最长公共子序列和改进的快速排序，最后两个果然没考，摆了摆了不补了（躺）
