1 条题解
-
0
#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
- 上传者