本文共 2099 字，大约阅读时间需要 6 分钟。
5.抽签
抽签
X星球要派出一个5人组成的观察团前往W星。
其中：
A国最多可以派出4人。
B国最多可以派出2人。
C国最多可以派出2人。
....
那么最终派往W星的观察团会有多少种国别的不同组合呢？
下面的程序解决了这个问题。
数组a[] 中既是每个国家可以派出的最多的名额。
程序执行结果为：
DEFFF
CEFFF
CDFFF
CDEFF
CCFFF
CCEFF
CCDFF
CCDEF
BEFFF
BDFFF
BDEFF
BCFFF
BCEFF
BCDFF
BCDEF
....
题目要求打印种类：
#include#define N 6#define M 5#define BUF 1024int sum;void f(int a[], int k, int m, char b[]){ int i,j; if(k==N){ b[M] = '\0'; if(m==0){ printf("%s\n",b); ++sum; } return; } for(i = 0; i <= a[k]; i++){ for(j = 0; j < i; j++) b[M-m+j] = k+'A'; f(a,k+1,m-j,b); }}int main(){ int a[N] = {4,2,2,1,1,3}; //int a[N] = {1,1,1,1,1,1}; char b[BUF]; f(a,0,M,b); printf("sum = %d\n",sum); return 0;}
我的思考：这里的dfs 可以按照权重选择（即每种人可选择数量不相同）
#include#define N 3#define M 5int res[8];int sum;void f(int a[], int k, int m){ int i,j; if(k==N){ if(m==0){ for(int i = 0; i < 5; ++i){ printf("%d",res[i]); } printf("\n"); ++sum; } return; } //这里只是简单的记录为k+1其实可以为其它的（比如数组num[i]） for(i = 0; i <= a[k]; i++){//第k个位置可以选择 0 到 a[k] 个 for(j = 0; j < i; j++) res[M-m+j] = k+1;//核心 M-m表示当前选择情况（5个位置）有几个位置已经确定 f(a,k+1,m-j); }}/* 可以产生不同权重的组合方式 例如 表示权重的数组 a 其含义是: 第一种可以最多有4个 第二种最多3个 第三种最多2个 但是三种之和最多选择 5个（M == 5） 的总种类数 */int main(){ int a[N] = {4,3,2}; //分配权重 f(a,0,5); printf("sum = %d\n",sum); return 0;}
另一种写法：
#include#include using namespace std;const int N = 6;//供选择的种类 int num[6] = {4,2,2,1,1,3};const int M = 5;//选取的人数 vector vec;int ans;int sum;void dfs(int pos){ if(sum == M){ for(int i = 0; i < vec.size(); ++i){ int cur = vec[i]; putchar(char('A'+cur)); } putchar('\n'); ++ans; return ; } if(sum > M || pos >= N) return; for(int i = 0; i <= num[pos]; ++i){ sum += i; //该类选择 i个 for(int j = 0; j < i; ++j) //记录该类 vec.push_back(pos); dfs(pos+1); sum -= i; for(int j = 0; j < i; ++j) //回溯 vec.pop_back(); }}int main() { ans = sum = 0; dfs(0); return 0; }
转载地址：http://eqimi.baihongyu.com/