暴力出奇迹，骗分过样例！！
DP
背包（时间，空间复杂度最优）
1.01背包
/*
01背包问题
f[j]表示放置总体积为j的包中的最大总价值
result = max([0...V])
状态转移方程f[j]:
1、不选取第i个物品： f[j] = f[j]
2、选取第i个物品： f[j] = f[j-v[i]] + w[i]
f[0][0] = 0;
*/
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 10010;
int m,n;
int f[N];//状态转移
int v[N],w[N];//体积、价值
int 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=m; j>=v[i]; j--){//枚举体积!!!逆序 更新!!!
f[j] = max(f[j], f[j-v[i]] + w[i]);
}
}
cout<<f[m]<<endl; //最大值
return 0;
}
2.完全背包
/*
完全背包问题 （物品数量无限）
f[j]表示放置总体积为j的包中的最大总价值
result = max(f[0...V])
状态转移方程f[j]:
f[j] = max(f[j], f[j-v[i] + w[i]);
f[0...V] = 0;
*/
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 10010;
int m,n;
int f[N];//状态转移
int v[N],w[N];//体积、价值
int 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=v[i]; j<=m; j++){//枚举体积
f[j] = max(f[j], f[j-v[i]] + w[i]);//状态转移
}
}
cout<<f[m]<<endl; //找最大值
return 0;
}
3.多重背包(并不是最优！)
/*
完全背包问题 （物品数量无限）
f[i][j]表示放置前i种物品到总体积为j的包中的最大总价值
result = max(f[N][0...V])
状态转移方程f[i][j]:
f[i][j] = max(f(i-1, j-k*v[i])+k*w[i]); 0<=k<=s[i]
f[0][0...V] = 0;
*/
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1010;
int m,n;
int f[N][N];//状态转移
int v[N],w[N],s[N];//体积、价值、数量
int main()
{
cin>>n>>m;//总数量跟总体积
for(int i=1; i<=n; i++)
cin>>v[i]>>w[i]>>s[i];//体积、价值
for(int i=1; i<=n; i++) //枚举物品
{
for(int j=0; j<=m; j++) //枚举体积
{
for(int k=0; k<=s[i]; k++) //枚举数量
{
if(j>=k*v[i])
f[i][j] = max(f[i][j], f[i-1][j-k*v[i]] + k*w[i]);//状态转移
}
}
}
cout<<f[n][m]<<endl; //找最大值
return 0;
}
另外，多重背包还有两种优化方法：二进制优化和单调栈优化，作者在此不详述了。
bfs/dfs
走迷宫问题：
(最短路径：dfs+剪枝优化/bfs)
/*
迷宫最短路径（边权相等）——BFS
*/
#include <iostream>
#include <string>
#include <queue>
using namespace std;
int n, m;
string maze[110];//迷宫字符串数组
bool vis[110][110];//是否访问过
int dir[4][2] = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};//方向
bool in(int x, int y) {//判断元素是否在迷宫中
return 0 <= x && x < n && 0 <= y && y < m;
}
struct node{
int x;//x坐标
int y;//y坐标
int d;//起点到该坐标的步数
};
int bfs(int sx, int sy){//广度优先搜索
queue<node> q;
node temp;
temp.x=sx;
temp.y=sy;
temp.d=0;//起始节点
q.push(temp);
vis[sx][sy]=true;//已经访问过了
while(!q.empty()){
node now=q.front();//取出对头元素
q.pop();//出队
if(maze[now.x][now.y]=='T'){
return now.d;//到目标点了
}
for(int i=0; i<4; i++){//依次枚举四个方向
int tx = now.x + dir[i][0];
int ty = now.y + dir[i][1];
if(in(tx, ty) && maze[tx][ty]!='*' && !vis[tx][ty]){
vis[tx][ty]=true;
temp.x=tx; temp.y=ty; temp.d=now.d+1;//下一层结点入队
q.push(temp);
}
}
}
return -1;//没有路径
}
int main() {
cin >> n >> m;//输入迷宫的行和列数
for (int i = 0; i < n; i++) {
cin >> maze[i];//迷宫
}
int x, y;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (maze[i][j] == 'S') {
x = i, y = j;//找起点坐标
}
}
}
cout<<bfs(x,y)<<endl;
return 0;
}
//迷宫最短路径长度（dfs）
//最优性剪枝
#include <cstdio>
#include <iostream>
#include <string>
using namespace std;
int n, m;
const int maxn=110;
string maze[maxn];
bool vis[maxn][maxn];//访问数组
int dir[4][2]= {{-1, 0}, {0, -1}, {1, 0}, {0, 1}}; //方向数组
int ans=0x3f3f3f3f;//最短路径长度
bool in(int x, int y)
{
//判断是否在迷宫中
return 0<=x && x<n && 0<=y && y<m;
}
void dfs(int x, int y, int step)
{
//坐标x，坐标y，步数
if(step >= ans)
{
return;//如果已经不是最优则剪枝
}
if(maze[x][y]=='T') //到达终点
{
ans = step;
return;
}
for(int i=0; i<4; i++) //遍历下一步结点
{
int tx = x + dir[i][0];
int ty = y + dir[i][1];
if(in(tx, ty) && maze[tx][ty]!='*' && !vis[tx][ty])
{
//结点在迷宫中，且不是*，且没有被访问过
vis[x][y] = 1;//置为已经访问
dfs(tx, ty, step + 1);//深搜一步
vis[x][y] = 0;//回溯一步
}
}
return;
}
int main()
{
cin>>n>>m;
for(int i=0; i<n; i++)
cin>>maze[i];
int x, y;
for(int i=0; i<n; i++)
{
for(int j=0; j<m; j++)
{
if(maze[i][j]=='S')
{
x=i;
y=j;//找到起点
}
}
}
vis[x][y]=1;//置为已访问
dfs(x, y, 0);//从起点开始深搜
cout<<ans<<endl;
return 0;
}
八皇后问题
(抽象dfs+回溯的经典样例，共有92种解法)
#include<bits/stdc++.h>
using namespace std;
int a[10], ans;//存每一行皇后的列号
//标识列、左对角线、右对角线是否被占用
bool b[20], c[20], d[20];
void print(){//输出结果
cout<<"No. "<<ans<<endl;
for(int i=1; i<=8; i++){
for(int j=1; j<=8; j++){
if(a[i]==j) cout<<1<<" ";
else cout<<0<<" ";
}
cout<<endl;
}
}
void dfs(int i){
//放置第i行的皇后
if(i > 8){
ans++;//方案数++
print();
return;//返回上一层
}
for(int j=1; j<=8; j++){//八种选择
if(b[j]==0 && c[i+j]==0 && d[i-j+8]==0){
//该列、左对角线、右对角线
a[i] = j;//可以放皇后
b[j]=c[i+j]=d[i-j+8]=1;//置为已访问
dfs(i+1);//放置下一行的皇后
b[j]=c[i+j]=d[i-j+8]=0;//回溯一步
}
}
return;//子节点遍历结束；返回上一层
}
int main(){
dfs(1);//从第一行开始选皇后
return 0;
}
n皇后问题
#include<bits/stdc++.h>
using namespace std;
int n;
int __map[20][20];
int a[20], ans;
bool b[40], c[40], d[40];
void print()
{
for(int i=1; i<=n; i++)
{
for(int j=1; j<=n; j++)
{
if(a[i]==j) __map[i][j]=1;
else __map[i][j]=0;
}
}
for(int i=1; i<=n; i++)
{
for(int j=1; j<=n; j++)
{
cout<<__map[i][j]<<" ";
}
cout<<endl;
}
cout<<endl;
}
void dfs(int i)
{
if(i > n)
{
ans++;
print();
return;
}
for(int j=1; j<=n; j++)
{
if(b[j]==0 && c[i+j]==0 && d[i-j+n]==0)
{
a[i] = j;
b[j]=c[i+j]=d[i-j+n]=1;
dfs(i+1);
b[j]=c[i+j]=d[i-j+n]=0;
}
}
return;
}
int main()
{
cin>>n;
dfs(1);
cout<<ans<<endl;
return 0;
}
