【PTA】凑零钱

分手后的思念是犯贱 2023-07-03 02:38 69阅读 0赞

#### 题目重述 ####

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

#### 输入格式： ####

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

#### 输出格式： ####

在一行中输出硬币的面值 V1 ≤V2 ≤⋯≤Vk ，满足条件 V1 +V2 +…+Vk =M。数字间以 1 个空格分隔，行首尾不得有多余空格。若解不唯一，则输出最小序列。若无解，则输出 No Solution。

注：我们说序列\{ A\[1\],A\[2\],⋯ \}比\{ B\[1\],B\[2\],⋯ \}“小”，是指存在 k≥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

#### 题解 ####

这道题可以说是一个0-1背包问题或者回溯法典型例题，使用`回溯法的算法框架`(其实回溯法的核心就是深度优先搜索)，找到符合条件的输出就可以。

需要注意的是，这道题让求最小序列，我们需要提前将数组排序，然后再进行回溯法求解，求出来的第一组符合条件的序列就是我们要求的最小序列。

如果你得测试点超时，你可以通过两种方式排查：

*  是否判断 所有的钱币面额加起来都小于m
 *  你的递归终止条件是否合理，是否做了无用功。

#### C++ AC ####

#include <iostream>
    #include <bits/stdc++.h>
    using namespace std;
    int n,m;
    int current=0;
    int arr[10010];
    bool isFind=false;//是否已经找到
    bool flag[10010];
    void find_(int i)
    {
        
        if(i==n)
        {
        
            return;
        }
    
    	if (current> m)
        {
        
            return ;
        }
        current+=arr[i];
        flag[i]=true;
        if(isFind)
        {
        
            return;
        }
        if(current==m)//找到了
        {
        
            for(int j=0; j<n; j++)
            {
        
                if(flag[j])//如果我们要这个
                {
        
                    if(!isFind)//如果是第一次输出
                    {
        
                        cout<<arr[j];
                        isFind=true;
                    }
                    else
                    {
        
                         cout<<" "<<arr[j];
                    }
                }
            }
        }
        else
        {
        
            find_(i+1);
        }
        //回溯到之前的状态
        current-=arr[i];
        flag[i]=false;
        //递归下一个
        find_(i+1);
        return;
    }
    int main()
    {
        
        int sum=0;
        memset(flag,0,sizeof(flag));
        cin>>n>>m;
        for(int i=0; i<n; i++)
        {
        
            cin>>arr[i];
            sum+=arr[i];
        }
        if(sum<m)
        {
        
            cout<<"No Solution";
        }
        else
        {
        
            sort(arr,arr+n);
            find_(0);
            if(!isFind)
            {
        
                cout<<"No Solution";
            }
        }
        return 0;
    }