L3-001 凑零钱 (30 分)「爆搜」或 「01背包 + 输出路径」

L3-001 凑零钱 (30 分)

题目描述：

给你n种货币，每种只能用一次，问能不能凑出m元，输出字典序最小的

思路1：「爆搜yyds」

因为M很小，才100，所以剪枝的作用很大，排序以后爆搜就行

注意特判一下这n个数的和与m的关系，如果小于m，则一定不可以凑出来，直接输出就行，不然会TLE在最后一个点

#include<bits/stdc++.h>usingnamespace std;#defineendl'\n'#defineinf0x3f3f3f3f#definemod71000000007#definemod9998244353#definem_p(a,b)make_pair(a, b)#definemem(a,b)memset((a),(b),sizeof(a))#defineioios::sync_with_stdio(false); cin.tie(0); cout.tie(0)#definedebug(a) cout <<"Debuging...|"<< #a <<": "<< a <<"\n";typedeflonglong ll;typedef pair <int,int> pii;#defineMAX300000+50int n, m, k;int tr[MAX];
vector<int>ans, a;bool p;voiddfs(int id,int x){if(x > m || p || id > n +1)return;if(x == m){
        p =1;
        a = ans;return;}for(int i = id; i <= n;++i){if(p)break;
        ans.push_back(tr[i]);dfs(i +1, x + tr[i]);
        ans.pop_back();}}voidwork(){
    cin >> n >> m;int sum =0;for(int i =1; i <= n;++i){
        cin >> tr[i];
        sum += tr[i];}if(sum < m){
        cout <<"No Solution\n";return;}sort(tr +1, tr +1+ n);for(int i =1; i <= n;++i){if(tr[i]> m){
            n = i -1;break;}}dfs(1,0);if(!p)cout <<"No Solution\n";else{for(int i =0; i < a.size();++i){if(i)cout <<" ";
            cout << a[i];}
        cout << endl;}}intmain(){
    io;work();return0;}

思路2:「01背包 + 输出路径」

因为要字典序最小的，所以我们可以从大到小排个序，这样更新的时候是值小的后更新，输出的时候就是字典序最小的

dp[i][j]

表示前

i

个，花费价值为

j

的钱能得到的最大价值

开一个

vis[i][j]

数组，为1则表示前

i

个物品,体积为

j

时可以选

i

这个物品使的价值得到最大，更新

i

的时候，判断一下

dp[i][j]

与

dp[i-1][j - ar[i]]+ar[i]

的大小，如果能更新的话，就让

vis[i][j] = 1

输出路径的时候就倒着输出，看当前体积

v

和当前

id

的vis是否是1，是的话就选这个物品，并更新体积

#include<bits/stdc++.h>usingnamespace std;#defineendl'\n'#defineinf0x3f3f3f3f#definemod71000000007#definemod9998244353#definem_p(a,b)make_pair(a, b)#definemem(a,b)memset((a),(b),sizeof(a))#defineioios::sync_with_stdio(false); cin.tie(0); cout.tie(0)#definedebug(a) cout <<"Debuging...|"<< #a <<": "<< a <<"\n";typedeflonglong ll;typedef pair <int,int> pii;#defineMAX10000+50int n, m, k, x;int tr[MAX];int dp[MAX];bool vis[MAX][105];voidwork(){
    cin >> n >> m;for(int i =1; i <= n;++i)cin >> tr[i];sort(tr +1, tr +1+ n,greater<int>());for(int i =1; i <= n;++i){for(int j = m; j >= tr[i];--j){if(dp[j]<= dp[j - tr[i]]+ tr[i]){
                dp[j]= dp[j - tr[i]]+ tr[i];
                vis[i][j]=1;}}}if(dp[m]== m){
        vector<int>ans;int id = n;while(m){if(vis[id][m]){
                ans.push_back(tr[id]);
                m -= tr[id];}--id;}for(int i =0; i < ans.size();++i){if(i)cout <<" ";
            cout << ans[i];}
        cout << endl;}else cout <<"No Solution\n";}intmain(){
    io;work();return0;}