凑硬币(DFS+剪枝)xiaodangao

韩梅梅喜欢满宇宙到处逛街。现在她逛到了一家火星店里，发现这家店有个特别的规矩：你可以用任何星球的硬币付钱，但是绝不找零，当然也不能欠债。韩梅梅手边有 $1 0^{4}$ 枚来自各个星球的硬币，需要请你帮她盘算一下，是否可能精确凑出要付的款额。

输入格式：

输入第一行给出两个正整数： $N$ （ $\le 10^4$ ）是硬币的总个数， $M$ （ $\le 10^2$ ）是韩梅梅要付的款额。第二行给出 $N$ 枚硬币的正整数面值。数字间以空格分隔。

输出格式：

在一行中输出硬币的面值 $V_1 \le V_2 \le \cdots \le V_k$ ，满足条件 $V_{1} + V_{2} + . . . + V_{k} = M$ 。数字间以 1 个空格分隔，行首尾不得有多余空格。若解不唯一，则输出最小序列。若无解，则输出 No Solution。

注：我们说序列{ $A[1], A[2], \cdots$ }比{ $B[1], B[2], \cdots$ }“小”，是指存在 $k \ge 1$ 使得 $A [i] = B [i]$ 对所有 $i < k$ 成立，并且 $A [k] < B [k]$ 。

输入样例 1：

8 9
5 9 8 7 2 3 4 1

输出样例 1：

1 3 5

输入样例 2：

4 8
7 2 4 3

输出样例 2：

No Solution

思路：这题果断想到利用sort排序(题目要求若有若干个，求字典序最小的)进行dfs，当当前sum+剩余所有可加和小于m时，果断返回false，当当前sum+当前最小可能取值>m时果断返回false，经典可行性剪枝；
代码如下：

/*************************************************************************
    > File Name: problem1.cpp
# Author: Badwoman
# mail: 1194446133@qq.com
    > Created Time: 2020年11月26日 星期四 19时11分46秒
 ************************************************************************/

#include<set>
#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<map>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
using namespace std;
const int N = 1e4+10;
int n,m,arr[N],sum[N];bool st[N];int ans[N],cnt;
bool dfs(int now,int nowsum,int deep){
    nowsum += arr[now];
    ans[deep] = arr[now];
    if(nowsum == m){
        cnt = deep ;return true;
    }
    if(nowsum + sum[n] - sum[now]<m||m - nowsum <arr[now+1])return false;
    for(int i=now+1;i<=n;++i){
        if(dfs(i,nowsum,deep+1)==true)return true;
    }
    return false;
}
void solve(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)scanf("%d",&arr[i]),sum[i] = sum[i-1] + arr[i];
    sort(arr+1,arr+1+n);bool flag = false;
    for(int i=1;i<=n;++i){
        if(dfs(i,0,1)){flag = true;
            for(int j=1;j<=cnt;++j)printf("%d%c",ans[j],j==cnt?'\n':' ');break;
        }
    }
    if(flag == false)puts("No Solution");
}
int main(){
    solve();
    return 0;
}

本文采用署名-非商业性使用-相同方式共享 4.0 国际许可协议，转载请注明出处。