L3-001 凑零钱

L3-001 凑零钱

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

输入格式：

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

输出格式：

在一行中输出硬币的面值 _V_1​≤_V_2​≤⋯≤_V__k_​，满足条件 _V_1​+_V_2​+…+_V__k_​=_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

分析

01背包问题，如果最后dp[m] == m，即为有解，反之无解，用一个数组去记录我们每次的更新，就可以输出序列（因为是从大往小找，所以一定是最小序列）

代码实现

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int dp[105], w[10023]; // 01背包
bool ischoice[10023][105];

bool camp(int &x, int &y)
{
    return x > y;
}

int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; ++i)
        cin >> w[i];
    sort(w, w + n, camp);
    for (int i = 0; i < n; ++i)
        for (int j = m; j >= w[i]; --j)
        {
            if (dp[j] <= dp[j - w[i]] + w[i])
            {
                ischoice[i][j] = 1; // 记录下来在这个地方选择了这个钱币
                dp[j] = dp[j - w[i]] + w[i];
            }
        }
    if (dp[m] != m)
        cout << "No Solution";
    else
    {
        vector<int> ans;
        int v = m, index = n;
        while (v > 0)
        {
            if (ischoice[index][v])      // 因为之前记录了我们的选择，所以我们每次遍历数组的列
            {                            // 从m列开始，找到我们存入了哪一个硬币才使得总额到 m
                ans.push_back(w[index]); // 将这个钱币存入vector
                v -= w[index];           // 那么，搜索的列自然就要到 当前值 - 刚刚存入硬币值 的那一列了
            }
            index--;
        }
        for (int i = 0; i < ans.size(); ++i)
            printf(i == ans.size() - 1 ? "%d" : "%d ", ans[i]);
    }
    return 0;
}

// DFS 暴力方法

// #include <iostream>
// #include <algorithm>

// using namespace std;

// int n, m, total, flag = 0, cnt = 0;
// int arr[10010];
// int ans[10010];

// void dfs(int pos, int sum) // dfs 遍历钱币
// {
//     if(sum > m) // 大于m就剪枝
//         return ;
//     if(sum == m)
//     {
//         flag = 1;
//         for(int i = 0; i < cnt; ++i)
//             printf(i == cnt - 1 ? "%d" : "%d ", ans[i]);
//         return ;
//     }
//     for(int i = pos; i < n; ++i) // 从当前位置到最后一个钱币
//     {
//         ans[cnt++] = arr[i]; // 加入队列
//         dfs(i + 1, sum + arr[i]);// 递归运算
//         if(flag)
//             return ;
//         cnt--; // 记得回退状态
//     }
// }

// int main()
// {
//     cin >> n >> m;
//     for(int i = 0; i < n; ++i)
//     {
//         cin >> arr[i];
//         total += arr[i];
//     }
//     if(total < m)
//         cout << "No Solution";
//     else
//     {
//         sort(arr, arr + n);
//         dfs(0, 0);
//         if(!flag)
//             cout << "No Solution";
//     }
//     return 0;
// }