题解

题目难度：中等难度

知识点：查找、数组、动态规划

解析问题：本题可以分析为典型的01背包问题，使用动态规划就可以解决问题。在分析问题时，主要解析为以下三步。
第一步：确定【状态】和【选择】。
在本题中，【状态】就是“剩余的总和”和“可选择的数”，【选择】就是“放入这个数”和“不放入这个数”。
第二步：要明确 dp 数组的定义。
第三步：根据【选择】，对状态转换的逻辑进行计算。

二维动态规划求解

第二步定义数组意义：在这里，使用二维的思维创建dp的形式。设置 dp[i][j] = true 或者 false ，表示前 i 个数的总和是否等于 j 。
第三步分析逻辑：如果不把 nums[i] 算入子集，那么是否能够恰好等于总和，取决于上一个状态 dp[i-1][j]。如果把 nums[i] 算入子集，那么是否能够恰好等于总和，取决于状态 dp[i - 1][j-nums[i-1]]。

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int N,M;
    cin>>N;
    vector<int> Prices;
    for(int i = 0; i< N; ++i)
    {
        int price;
        cin>>price;
        Prices.push_back(price);
    }
    cin>>M;
    //创建dp的状态
    vector<vector<bool>> dp(N+1,vector<bool>(M+1,false));
    //对边缘数据进行设定
    for (int i = 0; i <= N; ++i)
        dp[i][0] = true;

    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= M; ++j) {
            if (j - Prices[i - 1] < 0) {
               // 数值过高，不能购买
                dp[i][j] = dp[i - 1][j]; 
            } else {
               // 购买或不购买
                dp[i][j] = dp[i - 1][j] | dp[i - 1][j-Prices[i-1]];
            }
        }
    }
    cout<< dp[N][M]<<endl;
    return 0;
}

一维动态规划求解

为了更好的节约空间上的复杂度，在观察上述的dp[i][j]的等式时，可以总结出dp[i][j]始终是跟dp[i-1][...]成相关性的，因此可以进行一个维度的降低处理。

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int N,M;
    cin>>N;
    vector<int> Prices;
    for(int i = 0; i< N; ++i)
    {
        int price;
        cin>>price;
        Prices.push_back(price);
    }
    cin>>M;
    //创建dp的状态
    vector<bool> dp(M + 1, false);
    // base case
    dp[0] = true;
    for (int i = 0; i < N; i++) 
        for (int j = M; j >= 0; j--) 
            if (j - Prices[i] >= 0) 
                dp[j] = dp[j] || dp[j - Prices[i]];
    cout<< dp[M]<<endl;
    return 0;
}