实验一、分治法实验
本次实验要求采用分治算法和递归算法实现对一个序列的二叉查找算法、找最大值和最小值算法、归并排序算法，以及以最后一个元素作为基准元素的快速排序算法。

#include <bits/stdc++.h>
using namespace std;
//IOS
#define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
//长整型
#define int long long
int n;
const int N = 100010;
int a[N];
int tmp[N];
int find_left(int x){
	int l = 0, r = n - 1;
	while(l < r){
		int mid = l + r >> 1;
		if(a[mid] >= x) r = mid;
		else l = mid + 1;
	}
	if(a[l] == x) return l;
	return -1;
}
int find_right(int x){
	int l = 0, r = n - 1;
	while(l < r){
		int mid = l + r + 1 >> 1;
		if(a[mid] <= x) l = mid;
		else r = mid - 1;
	}
	if(a[l] == x) return l;
	return -1;
}
void Binary_Search(){
	cout << "length:";
	cin >> n;
	cout << "array:";
	for(int i = 0; i < n; i++){
		cin >> a[i];
	}
	sort(a, a + n);
	cout << "sorted array:";
	for(int i = 1; i <= n; i++) cout << a[i - 1] << " \n"[i == n];
	cout << "target:";
	int t;
	cin >> t;
	cout << "left binary search:";
	int res = find_left(t);
	if(res != -1) cout << "在" << res + 1 << "处" << endl;
	else cout << "不存在" << endl;
	cout << "right binary search:";
	res = find_right(t);
	if(res != -1) cout << "在" << res + 1 << "处" << endl;
	else cout << "不存在" << endl;
}

int* find_max(int q[], int l, int r){
	if(l >= r) return &q[l];
	int mid = l + r >> 1;
	int *a = find_max(q, l, mid), *b = find_max(q, mid + 1, r);
	return *a >= *b ? a : b;
}
int* find_min(int q[], int l, int r){
	if(l >= r) return &q[l];
	int mid = l + r >> 1;
	int *a = find_min(q, l, mid), *b = find_min(q, mid + 1, r);
	return *a <= *b ? a : b;
}
void FindMaxAndMin(){
	cout << "length:";
	cin >> n;
	cout << "array:";
	for(int i = 0; i < n; i++){
		cin >> a[i];
	}
	int* pos = find_max(a, 0, n - 1);
	cout << "max element:" << *pos << " pos:" << pos - a + 1 << endl;
	pos = find_min(a, 0, n - 1);
	cout << "min element:" << *pos << " pos:" << pos - a + 1 << endl;
}

void merge_sort(int q[], int l, int r){
	if(l >= r) return ;
	int mid = l + r >> 1;
	merge_sort(q, l, mid), merge_sort(q, mid + 1, r);
	
	int k = 0, i = l, j = mid + 1;
	while(i <= mid && j <= r){
		if(q[i] <= q[j]) tmp[k ++] = q[i ++];
		else tmp[k ++] = q[j ++];
	}
	
	while(i <= mid ) tmp[k ++] = q[i ++];
	while(j <= r ) tmp[k ++] = q[j ++];
	for(i = l, j = 0; i <= r; i++, j++) q[i] = tmp[j];
}
void Merge_Sort(){
	cout << "length:";
	cin >> n;
	cout << "array:";
	for(int i = 0; i < n; i++){
		cin >> a[i];
	}
	merge_sort(a, 0, n - 1);
	cout << "sorted array:";
	for(int i = 1; i <= n; i++) cout << a[i - 1] << " \n"[i == n];
}

void quick_sort(int q[], int l, int r) {
	if (l >= r) return;
	int x = q[r], i = l - 1, j = r;  
	while (i < j) {
		do j--; while (q[j] > x);  // 先移动右指针
		do i++; while (q[i] < x);  
		if (i < j) swap(q[i], q[j]);
	}
	swap(q[i], q[r]);              
	quick_sort(q, l, i - 1);       // 左半区：l 到 i-1
	quick_sort(q, i + 1, r);       // 右半区：i+1 到 r（修正递归区间）
}
void Quick_Sort(){
	cout << "length:";
	cin >> n;
	cout << "array:";
	for(int i = 0; i < n; i++){
		cin >> a[i];
	}
	quick_sort(a, 0, n - 1);
	cout << "sorted array:";
	for(int i = 1; i <= n; i++) cout << a[i - 1] << " \n"[i == n];
}

void showMainMenu(){
	cout 
	<< "\n=============== 主菜单 ===============\n"
	<< "1. 二叉查找算法\n"
	<< "2. 找最大值和最小值算法\n"
	<< "3. 归并排序算法\n"
	<< "4. 以最后一个元素作为基准元素的快速排序算法\n"
	<< "0. 退出程序\n"
	<< "========================================\n";
}
signed main(){
	int choice;
	bool exitFlag = false;
	do{
		showMainMenu();
		
		cout << "input:";
		// 输入验证
		if (!(cin >> choice)) {
			cout << "\n错误：必须输入数字！\n";
			cin.clear(); // 清除错误状态
			cin.ignore(numeric_limits<streamsize>::max(), '\n'); // 清空缓冲区
			continue;
		}
		
		switch (choice) {
		case 1:
			Binary_Search();
			break;
		case 2:
			FindMaxAndMin();
			break;
		case 3:
			Merge_Sort();
			break;
		case 4:
			Quick_Sort();
			break;
		case 0:
			exitFlag = true;
			std::cout << "程序已退出\n";
			break;
		default:
			cout << "错误：无效选项，请重新输入\n";
		}
	} while (!exitFlag);
	return 0;
}

实验二、动态规划法实验
给定背包承重量和n件物品，各个物品的重量和价值已知。选择装入背包的物品，使得装入的总价值最大。采用自底向上的动态规划方法解决0-1背包问题。本实验共2学时。

#include <bits/stdc++.h>
using namespace std;
//IOS
#define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
//长整型
#define int long long
const int N = 1010;

int n, m;
int v[N], w[N];
int f[N][N];
bool selected[N];
//int f[N];

signed main(){
	cin >> n >> m;
	for(int i = 1; i <= n; i++) cin >> v[i] >> w[i];
	//二维做法
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++){
			f[i][j] = f[i - 1][j];//不选的情况
			//当体积足够可以放下，选花费v[i]的体积，获得w[i]的价值
			if(j >= v[i]) f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
		}
	cout << f[n][m] << endl;
	
	for(int i = 0; i <= n; i++)
		for(int j = 0; j <= m; j++)
			cout << f[i][j] << " \n"[j == m];
	
	int t = m;
	for(int i = n; i >= 1; i--){
		if(f[i][t] != f[i - 1][t]){
			selected[i] = true;
			t -= v[i];
		}
	}
	
	for(int i = 1; i <= n; i++){
		cout << (selected[i]? "1":"0") << ' ';
	}
	return 0;
}

实验三、贪心法实验
本次实验要求采用贪心算法实现背包问题。所谓背包问题就是在0-1背包问题的基础上，如果考虑每件物品都是可分的，即可以选择装入某件物品的一部分而不是必须全部装入某件物品，则可以对物品按照单位价值递减排序，然后依次装入，直至背包满为止。本实验共2学时。

#include <bits/stdc++.h>
using namespace std;
//IOS
#define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
//长整型
#define int long long
const int N = 1010;
typedef struct Item{
	int index;
	int weight;
	int value;
	double ratio;
	bool operator< (const Item &t)const{
		return ratio > t.ratio;
	}
}Item;
Item items[N];
int selected[N];
int n, m;

signed main(){
	cin >> n >> m;
	for(int i = 1; i <= n; i++){
		int weight, value;
		cin >> weight >> value;
		double ratio = (double)value/weight;
		Item t = {i, weight, value, ratio};
		items[i] = t;
	}
	sort(items + 1, items + 1 + n);
	for(int i = 1; i <= n; i++){
		cout << items[i].index << ' ' << items[i].weight << ' ' <<items[i].value << ' ' <<items[i].ratio << endl;
	}
	double res = 0;
	int i = 1;
	while(m > 0 && i <= n){
		if(m >= items[i].weight){
			selected[items[i].index] = items[i].weight;
			res += items[i].value;
			m -= items[i].weight;
		}
		else{
			selected[items[i].index] = m;
			res += m * items[i].ratio;
			break;
		}
		i++;
	}
	cout << res << endl;
	for(int i = 1; i <= n; i++){
		cout << selected[i] << ' ';
	}
	return 0;
}

实验四、回溯法实验
本次实验要求采用回溯算法实现0-1背包问题。所谓0-1背包问题（同实验二）。本实验共2学时。

#include <bits/stdc++.h>
using namespace std;
//IOS
#define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
//长整型
#define int long long
const int N = 1010;
int v[N],w[N];
int n, m;

int max_value;          // 记录当前最大价值
bool selected[N]; // 当前递归路径的选择状态
bool selecteds[N][N]; // 最优解的选择状态 selecteds[2^N][N];
int ii = 1;
void dfs(int idx, int v1, int w1) {
	// 处理完所有物品，检查是否更新最优解
	if (idx > n) {
		if(w1 > max_value){
			max_value = w1;
		}
		if(w1 <= max_value){
			for (int i = 1; i <= n; i++) {
				selecteds[ii][i] = selected[i];
			}
			ii++;
		}
		return ;
	}
	// 不选当前物品
	dfs(idx + 1, v1, w1);
	// 选当前物品（若能放入）
	if (v1 + v[idx] <= m) {
		selected[idx] = true; // 选择当前物品
		dfs(idx + 1, v1 + v[idx], w1 + w[idx]);
		selected[idx] = false; // 回溯，撤销选择
	}
}

signed main(){
	cin >> n >> m;
	for(int i = 1; i <= n; i++) cin >> v[i] >> w[i];
	
	dfs(1, 0, 0);
	
	cout << max_value << endl;
	for(int i = 1; i<ii; i++){
		for(int j = 1; j<=n; j++){
			cout << (selecteds[i][j]? "1":"0") <<" \n"[j == n];
		}
	}
	return 0;
}