L3-001 凑零钱

题目链接

L3-001 凑零钱**

分析

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;
// }