算法填充题

子集生成问题

• 问题描述

子集生成是暴力求解算法中比较经典的问题，给出集合Ａ，求得相应的子集，进行打印。

• 解法一：增量构造法

#include
#include
#include
#include
using namespace std;
#define INF 300 
int A[100]; 
void print_subset(int n,int *A,int cur)
{
	for(int i=0;i<cur;i++)
		printf("%d ",A[i]);//输出子集 当前的集合 
	printf("n");
	int s=cur?A[cur-1]+1:0;//确定当前最小的可能值  如果这里不是 这里特殊的就是cur==0时 其他的就是选比前一个大1的 
	for(int i=s;i<n;i++)
	{
		A[cur]=i;//将i加入当前的集合
		print_subset(n,A,cur+1);// 递归构造子集 
	 } 
}
int main()
{
	int n;scanf("%d",&n);
	print_subset(n,A,0); 
}

• 解法二：位向量法

#include
#include
#include
#include
using namespace std;
#define INF 300 
int B[100]; 
void print_subset(int n,int *B,int cur)
{
	if(cur==n)
	{
		for(int i=0;i<cur;i++)
			if(B[i])printf("%d ",i);
		printf("n");
		return ;
	}
	B[cur]=1;
	print_subset(n,B,cur+1);//选 
	B[cur]=0;
	print_subset(n,B,cur+1);//不选 
}
int main()
{
	int n;scanf("%d",&n);
	print_subset(n,B,0); 
}

• 解法三：二进制法(简单)

#include
#include
#include
#include
using namespace std;
#define INF 300 
int B[100]; 
void print_subset(int n,int s)
{
	for(int i=0;i<n;i++)
		if(s&(1<<i))printf("%d ",i);
	printf("%n");
}
int main()
{
	int n;scanf("%d",&n);
	for(int i=0;i<(1<<n);i++)
		print_subset(n,i); 
}
原文链接：https://blog.csdn.net/liyanfeng1996/article/details/52821868

全排列生成问题

• 问题描述

对于给定的集合A{a1,a2,…,an},其中的n个元素互不相同，如何输出这n个元素的所有排列（全排列）。

• 算法实现 (递归)

#include 
using namespace std;
const int maxn=1000;
int a[maxn];
void swap(int i,int j)
{
    int temp=a[i];
    a[i]=a[j];
    a[j]=temp;
}
void perm(int k,int m,int pk,int pm)//k,m一般取起始和终点位置，k是不断变化的
{
    //k是中间变量，m初始化为参与拍列元素的起始坐标和终止坐标
    //pk和pm分表表示参与排列元素的起始和终止坐标，不变的量。
    if(k==m){//当k换到最后的时候，便是出口，是已经交换好的序列
        for(int i=pk;i<=pm;i++) cout<<a[i];
        cout<<endl;
    }
    else{
        for(int i=k;i<=m;i++){
            swap(k,i);//一部分一部分的交换，最后进行还原
            perm(k+1,m,pk,pm);//模拟一下过程，一开始求解N确定一个元素后，求解N-1，依次类推。
            swap(k,i);//还原
        }
    }
}
int main()
{
    int x;
    cin>>x;
    for(int i=1;i<=x;i++)
        a[i]=i;
    perm(1,x,1,x);
    return 0；
}
原文链接：https://blog.csdn.net/qq_29980371/article/details/72553303

哈密顿回路问题

• 问题描述

• 算法
  

• 算法实现

采用邻接矩阵存储，数组 arc[n][n] 存储顶点之间的边的情况，为了避免在函数之间传递参数，将数组arc设为 全局 变量，设数组 x[n] 表示哈密顿回路经过的顶点。

八皇后问题

• 问题描述

在8 x 8的棋盘上摆放8个皇后，而且八个皇后中的任意两个是不能处于同一行、同一列、或同一斜线上。也可以拓展到n皇后问题，即在n✖n的棋盘上摆放n个皇后，使任意两个皇后都不能处于同一行、同一列或同一斜线上。

• 算法
  

• 算法实现

皇后k摆放在k行x[k]列的位置

最大子段和问题

• 问题描述
  
• 算法实现

变量center表示序列的中间位置，数组 a[n] 存放整数序列

最长公共子序列问题

• 问题描述
  
• 算法实现
  

综合题

1. 贪心法（设计+证明）

贪心算法的设计思想：

• 贪心算法在解决问题的策略上目光短浅，只根据当前已有的信息就做出选择，而且一旦做出了选择，不管将来有什么结果，这个选择都不会改变。换言之，贪心法并不是从整体最优考虑，它所做出的选择只是在某种意义上的局部最优。贪心算法对于大部分的优化问题都能产生最优解，但不能总获得整体最优解，通常可以获得近似最优解。

贪心算法的证明：

2.0/1背包问题（证明+动态规划法计算过程）

• 证明（反证法）
  
• 动态规划法计算过程

3.货币兑付问题（证明+动态规划法计算过程）

• 题目： 在面值为(v1, v2, …, vn)n种货币中，需要支付y值的货款，应如何支付才能使货币支付的张数最少。设计动态规划算法求解该问题。

• 证明
  

• 解决
  
  示例：面值(1, 2, 5, 10)，支付8
  
  示例：面值(2, 5, 10)，支付8
  

4.多段图最短路径问题（证明+动态规划法计算过程）

• 问题

• 证明

• 动态规划法计算过程
  
  

5.多机调度或批处理调度（限界函数设计+搜索过程）

• 问题描述
  

• 限界函数设计
  
  

• 搜索过程
  
  （1)在根结点，将sum1和sum2分别初始化为0,估算目标函数的上界为41,将根结点加入待处理结点表PT.
  

6.TSP问题（搜索空间树及算法）

• 问题描述 假设有一个旅行商要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。旅行商有一个要访问城市的列表和每两个城市之间旅行的开销。需要求出开销最短的一种走法。
• 搜索空间树
  
• 算法