收银员现有 n 张面值分别为 v1,v2,…,vn 的纸币。若找零金额为 m,则一共有多少种找零方法?
注:0<n≤1000,0<v1,v2,…,vn≤10000,0<m≤10000
输入格式
输出格式
1 2
| 若有解,则输出全部找零方案,每输出一种 若无解,则输出“None”
|
输入样例1
输出样例1
输入样例2
输出样例2
解题思路
通过分析题目可知,我们可以将手中n个钞票面值的子集做相加,让和等于m。因此改题的解空间树是子集树。
定义 v[ ] 数组存放面值
book [ ] 数组记录,每一个元素的值是0或1,在子集树中代表该节点的两个分支。0 代表该层节点不放入子集中,1代表该节点放入子集中。
子集树的层数为 n+1 层,因为最后一层也需要判断是否进入子集,就会多一层分支。
扩展节点的约束条件是 n_num < m,只要当前选择的面值和小于找零总数 m ,就要深入子集树,寻找下一个节点。
扩展节点的限界条件是 n_num > m 或者 层数 i > n,代表当前子集面值和超过 m ,或者所有面值加起来小于 m。
一旦满足 n_num = m,就输出结果。
1 2 3
| book[i] = 0;
n_num -= v[i];
|
超出限界函数的回溯条件。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51
| #include <iostream> #include <algorithm> using namespace std;
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; }
|