1 条题解

  • 0
    @ 2026-1-27 19:52:12
    #include <bits/stdc++.h>
    using namespace std;
    
    int n,m,arr[100];        // [1] n-输入的整数个数;m-目标和;arr数组-存储输入的N个整数
    int dp[1000100]={};      // [2] dp数组-动态规划状态,dp[j]=1表示可以凑出和为j的子集,0表示不能
    
    int main() {
        // 问题分析:判断是否存在若干数的和等于M,这是典型的01背包问题(每个数只能选一次,目标容量为M)
        // 解题步骤:用dp数组记录每个可能的和是否可达,初始时和为0可达,再逐个加入数字更新可达状态
        
        cin>>n;
        for(int i=1;i<=n;i++) cin>>arr[i];  // [3] 读取输入的N个整数,存入arr数组
        cin>>m;                             // [4] 读取目标和M
        
        dp[0]=1;  // [5] 初始化:和为0是可达的(选择空集)
        // 01背包核心循环:遍历每个数字,逆序更新dp数组(避免重复选同一个数)
        for(int i=1;i<=n;i++){
            for(int j=m;j>=arr[i];j--){
                if(dp[j-arr[i]]){  // [6] 如果和为j-arr[i]可达,那么加上当前数arr[i]后,和为j也可达
                    dp[j]=1;       // [7] 标记和为j可达
                }
            }
        }
        
        if(dp[m]){  // [8] 检查目标和M是否可达
            cout<<"YES";
        }else{
            cout<<"NO";
        }
        return 0;
    }
    
    • 1

    信息

    ID
    1352
    时间
    1000ms
    内存
    256MiB
    难度
    10
    标签
    递交数
    1
    已通过
    1
    上传者