暴搜输出可行解

暴搜输出可行解

三水和小羽毛的sum点游戏

题目背景

三水和小羽毛玩腻了二十四点，她们决定玩点新东西。

小羽毛给出一个数字和以及 N N N个数字，由三水给出这 N N N个数字计算得出这个数字和的可能。

由于这是一个新游戏，为了不让三水花太多的时间，两人约定只做加法。

题目描述

小羽毛给出一个数字和 s u m ( s u m ≤ 1000 ) sum(sum≤1000) sum(sum≤1000)。

随后给出 N ( N ≤ 25 ) N(N≤25) N(N≤25)个数字的值，由三水从这 N N N个数字中任意选取（同一个数字只能选取一次）若干，使其和恰好等于 s u m sum sum

输入格式

第一行是两个数字：数字和 s u m sum sum以及可供三水挑选的数字数量 N N N

第二行有 N N N个正整数 a i a_i ai​

输出格式

输出可能的方案，多个方案则按照字典序输出，每个方案占一行

最后一行输出所有的可行方案总数

样例一

输入

3 3
1 1 1

输出

1 2 3
1

样例二

输入

5 5
4 1 2 3 1

输出

1 2
1 5
2 4 5
3 4
4

提示说明

s u m ≤ 1000 sum≤1000 sum≤1000， N N N≤25

题解

看上去是一个01背包，但是emmm这题用dp俺不会做（因为dp回溯只能解出一个最优解。。有没有更好的方法俺也不知道。。。）

因为需要输出所有解，所以这题我用的dfs暴搜+剪枝。

数组a存储所有数字的值，数组v标记某个数字是否选中，tol表示搜索进行到当前情况，已经选中的数字和。

剪枝策略：若当前的数字和tol已经大于目标值sum，剪枝。若当前数字已经全部遍历完则返回。

每次对第k个数字进行选，还是不选的抉择。

如果选中，则v[k]=1标记选中，然后递归dfs(k+1, tol + a[k])

如果不选，则v[k]=0标记不选，然后递归dfs(k+1, tol)

注意暴搜的时候，先搜当前数字“选中”的情况，再搜当前数字“不选”的情况。以达到“多个方案按照字典序输出”的目的

标程

#include<bits/stdc++.h>
using namespace std;
const int N = 30;
int a[N], v[N];
int sum, n, res = 0;
void printPlan(){			//输出可行解for(int i = 1; i <= n; i++)if(v[i])cout<<i<<" ";cout<<endl;
}
void dfs(int k, int tol){	//对第k个数字进行抉择，当前已经得到的和为tolif(tol == sum){			//可行解printPlan();res++;return;}if(k > n)				//剪枝return;if(tol > sum)			//剪枝return;v[k] = 1;				//注意先“选择”这个数字dfs(k + 1, tol + a[k]);v[k] = 0;				//后“不选”这个数字，以达到字典序输出dfs(k + 1, tol);
}
int main(){cin>>sum>>n;for(int i = 1; i <= n; i++)cin>>a[i];dfs(1, 0);			//从第1个数字开始选择，当前数字和为0cout<<res<<endl;return 0;
}