🎒 简单背包判定（子集和）

📘 题目描述

设有一个背包，其最大可承载重量为 s。现有 n 件物品，每件物品的重量为正整数 w₁, w₂, ..., wₙ。

请判断是否可以从这些物品中选出若干件，使得它们的总重量 ​**正好等于 s**​。

📥 输入格式

第一行包含两个整数：

s n

• s 表示背包容量（1 ≤ s ≤ 32767）
• n 表示物品数量（1 ≤ n ≤ 50）

第二行包含 n 个正整数，表示每件物品的重量 w₁, w₂, ..., wₙ。

📤 输出格式

• 如果存在一种选法能使得物品重量之和为 s，输出：

YES

• 否则输出：

NO

📌 输入样例

20 5
1 3 5 7 9

📌 输出样例

YES

💡 解题思路

本题为经典 ​子集和判定问题​，可以采用动态规划（DP）求解：

• 定义布尔数组 dp[i] 表示：是否能用某些物品组合出重量为 i；
• 初始状态：dp[0] = true；
• 状态转移：对每个物品 w，从后往前更新：

for (int i = s; i >= w; --i)
    dp[i] = dp[i] || dp[i - w];

• 最终看 dp[s] 是否为 true。