深度优先搜索——枚举组合

所谓枚举组合，其实就是从若干个选若干个数。
比如x[1],x[2],x[3],x[4],……x[n]每个数字时0（不选）和1（选）
x表示当前选到第几个书，dep表示选了几个数
对于每个数来说，它有选或不选两种可能，时间复杂度就是O(2^n)
核心代码：

int n, k;
int comb[N];
void dfs(int x, int dep) {
    if(dep == k) {
        for (int i = 0; i < k; i++) {
          cout << comb[i] << " ";
        }
        cout << endl;
        return;
    }
    if(x > n) {
        return ;
    }
    comb[dep] = x;
    dfs(x + 1, dep + 1);
    dfs(x + 1, dep);
}

找出从自然数 1、2……n（0<n<10）中任取 r(0<r≤n) 个数的所有组合。
输入格式
输入 n、r。
输出格式
按特定顺序输出所有组合。
特定顺序：每一个组合中的值从大到小排列，组合之间按逆字典序排列。

先考虑如果不按特定舒徐输出的程序应该是：
示例代码

#include <iostream>
using namespace std;
const int N = 15;
int n, k;
int comb[N];
void dfs(int x, int dep) {
    if(dep==k){
        for(int i=0;i<k;i++){
            cout<<comb[i];
        }
        cout<<endl;
        return;
    }
    if(x>n)
        return;
    comb[dep]=x;
    dfs(x+1,dep+1);
    dfs(x+1,dep);
}

int main()
{
    cin >> n >> k;
	dfs(1, 0);
    return 0;
}

但题目中要求按照字典序逆序排列，而现在是按照字典序排列，所以就应该是在找x的时候倒着找就可以了。
示例代码：

#include <iostream>
using namespace std;
const int N = 15;
int n, k;
int comb[N];
void dfs(int x, int dep) {
    if(dep==k){
        for(int i=0;i<k;i++){
            cout<<comb[i];
        }
        cout<<endl;
        return;
    }
    if(x<=0)
        return;
    comb[dep]=x;
    dfs(x-1,dep+1);
    dfs(x-1,dep);
}

int main()
{
    cin >> n >> k;
	dfs(n, 0);
    return 0;
}

这道题的中重点就是倒序，而倒序的重点就是为什么一i开始写的是正序。 ·

蒜头君来到文具店，选择了 k 支自己喜欢的水彩笔，并抄下了它们的价格。可是到结算时，他发现自己抄价格时抄得太密集，以至于所有价格连成了一个数字串。老板想和蒜头君开个玩笑，于是对他说：“你可以把这个数字串分成 k 段，代表这 k 支笔的价格，然后把他们加起来，就是你要付给我的钱了。”

当然，蒜头君想尽可能省下钱去买《算法导论》，所以请你来帮忙算算，他最少需要付多少钱。注意水彩笔的钱可以为 0 元。

数据范围：1≤k≤∣s∣≤8，s 仅包含数字 0∼9。

样例输入
72553
3
样例输出
85
先分析一下样例，就应该是7+25+53=85
现在来将一个比较奇特的思路，dfs过程中我们记录4个信息，dfs(int u,int x,int sum,int cnt）u表示现在枚举到第几位（字符串下表），x是现在枚举的价钱，sum是总价,cnt表示现在枚举了几根笔（段数）。
当前第u位有两种可能

1. 跟前面的合并
2. 独立的新数字
   1的情况就是x变更为now10+s[u]，sum不变
   2的情况就是x变更为0，sum变为sum+10x+s[u]

#include<iostream>
#include<cstring>
using namespace std;
int n,k,a[1005],ans=1e9,nownum;
string s;
void dfs(int u,int x,int sum,int cnt){
/*u表示处理到的数字
x表示由之前部分带来的数字
sum表示当前的数字
cnt表示已经选取了几个数字
当cnt=k且u=n时完事*/
if(u==n){
	if(cnt==0){
		ans=min(ans,sum+x);
	}
	return;
}
if(cnt<0)
	return;
dfs(u+1,x*10+a[u],sum,cnt);
dfs(u+1,0,sum+10*x+a[u],cnt-1);

}
int main(){
	cin>>s>>k;
	n=s.size();
	for(int i=0;i<n;i++)
		a[i]=(int)s[i]-'0';
	dfs(0,0,0,k-1);
	cout<<ans;
	return 0;
}

超级书架2：
展开
题目描述
Farmer John最近为奶牛们的图书馆添置了一个巨大的书架，尽管它是如此的大，但它还是几乎瞬间就被各种各样的书塞满了。现在，只有书架的顶上还留有一点空间。 所有N(1 <= N <= 20)头奶牛都有一个确定的身高H_i(1 <= H_i <= 1,000,000 - 好高的奶牛>_<)。设所有奶牛身高的和为S。书架的 高度为B，并且保证1 <= B <= S。 为了够到比最高的那头奶牛还要高的书架顶，奶牛们不得不象演杂技一般，一头站在另一头的背上，叠成一座“奶牛塔”。当然，这个塔的高度，就是塔中所有奶牛的身高之和。为了往书架顶上放东西，所有奶牛的身高和必须不小于书架的高度。 塔叠得越高便越不稳定，于是奶牛们希望找到一种方案，使得叠出的塔在高度不小于书架高度的情况下，高度尽可能小。你也可以猜到你的任务了：写一个程序，计算奶牛们叠成的塔在满足要求的情况下，最少要比书架高多少。

输入格式

• 第1行: 2个用空格隔开的整数：N 和 B
• 第2…N+1行: 第i+1行是1个整数：H[i]

输出格式

• 第1行: 输出1个非负整数，即奶牛们叠成的塔最少比书架高的高度

输入输出样例
输入 #1
5 16
3
1
3
5
6
输出 #1
1
说明/提示
输出说明:

我们选用奶牛1、3、4、5叠成塔，她们的总高度为3 + 3 + 5 + 6 = 17。任何方案都无法叠出高度为16的塔，于是答案为1。

dfs(int i,int s)状态表示现在第i位数字选还是不选，s表示当前的总和，这道题只需要输出有几种方案，而不用输出每种方案，这使得代码变得简单了许多
可以把这个看作一个搜索树

#include<iostream>
using namespace std;
int n,high,a[25],ans=1e9;
void dfs(int u,int hight){
	if(u==n+1){
		//cout<<hight<<" ";
		if(hight>=high){
			ans=min(ans,hight-high);
		}
		return;
	}
	dfs(u+1,hight+a[u]);
	dfs(u+1,hight);
}
int main(){
	cin>>n>>high;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	dfs(1,0);
	cout<<ans;
	return 0;
}

这道题目其实也可以用状压dp或背包啥的，但是这道题给的数字数量比较小，所以就没有必要了。