目录

问题 A: 全排列问题

 问题 B: 组合的输出

问题 C: 子集和问题

问题 D: 迷宫问题

问题 E: 装载问题

问题 A: 全排列问题

题目描述

要求计算从1到N的N个整数所能构成的所有排列，并按照字典顺序依次输出。

输入

输入为一组整数，每行为一个整数N，N<8，结尾行为0。

输出

对每一个输入N，按照字典序输出1到N的所有排列，数字中间用空格隔开，每个排列的输出占一行。

样例输入 

2
3
0

样例输出 

1 2 
2 1 
1 2 3 
1 3 2 
2 1 3 
2 3 1 
3 1 2 
3 2 1 

#include<bits/stdc++.h>
using namespace std;
#define int long longvector<int>ans;int fun(int n){if(ans.size()==n){for(int i=0;i<n;i++){cout<<ans[i]<<" ";}cout<<endl;}for(int i=1;i<=n;i++){if(find(ans.begin(),ans.end(),i)==ans.end()){ans.push_back(i);fun(n);ans.pop_back();}}return 0;
}signed main(){int n;while(1){ans.clear();cin>>n;if(n==0){break;}fun(n);}return 0;
}

 问题 B: 组合的输出

题目描述

排列与组合是常用的数学方法，其中组合就是从 n 个元素中抽出 r 个元素(不分顺序且 r<＝n)，我们
可以简单地将 n 个元素理解为自然数 1，2，…，n，从中任取 r 个数。
现要求你用递归的方法输出所有组合。

输入

一行两个自然数 n、r(1<n<21，1<＝r<＝n)。

输出

所有的组合，每一个组合占一行且其中的元素按由小到大的顺序排列，每个元素占三个字符的位置，所
有的组合也按字典顺序。

样例输入 复制

5 3

样例输出 复制

  1  2  31  2  41  2  51  3  41  3  51  4  52  3  42  3  52  4  53  4  5

提示

按%3d的格式输出

#include<bits/stdc++.h>
using namespace std;vector<int>ans;int fun(int n,int r){if(ans.size()==r){for(int i=0;i<ans.size();i++){printf("%3d",ans[i]);}cout<<endl;return 0;}for(int i=1;i<=n;i++){if(ans.size()!=0){while(ans.back()>=i){i++;}if(i>n){return 0;}}ans.push_back(i);fun(n,r);ans.pop_back();}return 0;
}int main(){int n,r;cin>>n>>r;ans.clear();fun(n,r);
}

问题 C: 子集和问题

题目描述

子集和问题的一个实例为〈S,t〉。其中，S={ x 1 ， x 2 ，…， x n }是一个正整数的集合，c是一个正整数。子集和问题判定是否存在S的一个子集S1，使得子集S1和等于c。对于给定的正整数的集合S={ x 1 ， x 2 ，…， x n }和正整数c，编程计算S 的一个子集S1，使得子集S1和等于c。

输入

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

输出

当问题有解时，输出满足条件的子集；当问题无解时，输出“No Solution!”。

样例输入 复制

5 10
2 2 6 5 4

样例输出 复制

2 2 6

提示

n<7000,c在int范围内。

注意找到后直接退出程序就行

#include<bits/stdc++.h>
#define int long long
using namespace std;bool flag;
int nums[7005];
bool a[7005];
vector<int>ans;
int all;int fun(int n,int c){if(all==c){for(int i=0;i<ans.size();i++){cout<<ans[i]<<" ";}cout<<endl;flag=true;exit(0);}if(all>c){return 0;}for(int i=1;i<=n;i++){while(a[i]==true){i++;}ans.push_back(nums[i]);a[i]=true;all+=nums[i];fun(n,c);ans.pop_back();a[i]=false;all-=nums[i];}return 0;
}signed main(){int n,c;scanf("%lld%lld",&n,&c);ans.clear();int temp=0;for(int i=1;i<=n;i++){scanf("%lld",&nums[i]);temp+=nums[i];}if(temp<c){cout<<"No Solution!"<<endl;return 0;}fun(n,c);if(!flag){cout<<"No Solution!"<<endl;}return 0;
}

问题 D: 迷宫问题

题目描述

设有一个 N*N(2<=N<10)方格的迷宫，入口和出口分别在左上角和右上角。迷宫格子中分别放 0 和 1，0 表示可通，1 表示不能，入口和出口处肯定是 0。迷宫走的规则如下所示：即从某点开始，有八个方向可走，前进方格中数字为 0 时表示可通过，为 1 时表示不可通过，要另找路径。找出所有从入口（左上角）到出口（右上角）的路径(不能重复)，输出路径总数，如果无法到达，则输出 0。

输入

第一行输入一个整数N
第二行到第N+1行，输入一个N*N的01矩阵，有空格隔开。

输出

若能到达，则输出路径总数；若不能到达，则输出0。

样例输入 复制

3
0 0 0
0 1 1
1 0 0

样例输出 复制

2

就是一个dfs 

#include<bits/stdc++.h>
#define int long long
using namespace std;const int N=10+5;
int n,mymap[N][N],sum=0; int mapx[N]={ 0, 1, 0,-1,-1, 1, 1,-1}; 
int mapy[N]={-1, 0, 1, 0,-1,-1, 1, 1};bool  dp[N][N];void dfs(int stepx,int stepy)
{if(stepx==0&&stepy==n-1){sum++;return;}for(int i=0;i<8;i++){int x,y;x=stepx+mapx[i];y=stepy+mapy[i];if(x>=0&&x<n&&y>=0&&y<n&&mymap[x][y]==0&&dp[x][y]==false) {dp[x][y]=true;dfs(x,y);dp[x][y]=false;	} }return; 
}signed main()
{cin>>n;for(int i=0;i<n;i++)for(int j=0;j<n;j++)cin>>mymap[i][j];dp[0][0]=true;dfs(0,0);cout<<sum;return 0;	
}

问题 E: 装载问题

题目描述

有一批共n个集装箱要装上艘载重量为c的轮船，其中集装箱i的重量为w i 。找出一种最优装载方案，将轮船尽可能装满，即在装载体积不受限制的情况下，将尽可能重的集装箱装上轮船。

输入

第一行有2个正整数n和c。n是集装箱数，c是轮船的载重量。接下来的1行中有n个正整数，表示集装箱的重量。

输出

输出最大装载重量

样例输入 复制

5 10
7 2 6 5 4

样例输出 复制

10

提示

n<=100,c<=1000

 就是一个01背包问题

#include<bits/stdc++.h>
using namespace std;int f[1005];
int w[1005];
int value[1005];
int num[1005];void fun(){int n,v;cin>>n>>v;for(int i=1;i<=n;i++){cin>>value[i];w[i]=value[i];}for(int i=1;i<=n;i++){for(int j=v;j>=w[i];j--){f[j]=max(f[j],f[j-w[i]]+value[i]);}}cout<<f[v]<<endl;
}int main(){fun();return 0;
}