【2022暑期训练-5】7-3 找零钱

HBUACM

收银员现有 n 张面值分别为 v1,v2,…,vn 的纸币。若找零金额为 m，则一共有多少种找零方法？

注：0<n≤1000，0<v1,v2,…,vn≤10000，0<m≤10000

n
v1,v2,...,vn
m

若有解，则输出全部找零方案，每输出一种
若无解，则输出“None”

输入样例1

6
3 1 4 3 2 7
9

输出样例1

3 1 3 2
3 4 2
4 3 2
2 7

输入样例2

5
5 3 4 6 7
2

输出样例2

None

通过分析题目可知，我们可以将手中n个钞票面值的子集做相加，让和等于m。因此改题的解空间树是子集树。

定义 v[ ] 数组存放面值

book [ ] 数组记录，每一个元素的值是0或1，在子集树中代表该节点的两个分支。0 代表该层节点不放入子集中，1代表该节点放入子集中。

子集树的层数为 n+1 层，因为最后一层也需要判断是否进入子集，就会多一层分支。

扩展节点的约束条件是 n_num < m，只要当前选择的面值和小于找零总数 m ，就要深入子集树，寻找下一个节点。

扩展节点的限界条件是 n_num > m 或者 层数 i > n，代表当前子集面值和超过 m ，或者所有面值加起来小于 m。

一旦满足 n_num = m，就输出结果。

book[i] = 0;

n_num -= v[i];

超出限界函数的回溯条件。

#include <iostream>
#include <algorithm>
using namespace std;
//典型回溯  dfs 
int m, n, n_num, sum = 0, v[1024], book[1024] = {0};//记录状态 

void println()
{
	int flag = false;
	for(int i = 1; i <= n; ++i)
	{
		if(book[i]) 
		{
			if(flag) putchar(' ');
			printf("%d", v[i]);
			flag = true;	
		}	
	}
	putchar('\n');
	++sum;	
} 

void Solveways(int i)
{
	if(n_num < m)
	{
		while(i <= n)
		{			
			if(!book[i])
			{
				book[i] = 1;
				n_num += v[i];
				Solveways(i + 1);
				book[i] = 0;
				n_num -= v[i];				
			}
			++i;
		}
	}
	else if(n_num == m) println();	
} 

int main()
{
	scanf("%d", &n);
	for(int i = 1; i <= n; ++i) scanf("%d", &v[i]);
	scanf("%d", &m);	
	Solveways(1);
	if(sum == 0) printf("None\n"); 
	return 0;	
}