题解 | 完全背包前置题

#include <iostream>
using namespace std;
using ll = long long;
const ll N = 1e3 + 5;
ll v[N];
bool dp[N];  // dp[j]表示“能否凑出总价值j”，true为可以，false为不可以

int main() {
    ll n, k;
    cin >> n >> k;
    for (ll i = 1; i <= n; i++) {
        cin >> v[i];
    }

    // 初始化dp数组：价值0不需要任何物品就能凑出，所以dp[0]=true；其他初始为false
    dp[0] = true;
    for (ll j = 1; j <= k; j++) {
        dp[j] = false;
    }

    // 完全背包的核心遍历：先遍历物品，再遍历背包容量（正序遍历容量，允许物品重复选取）
    for (ll i = 1; i <= n; i++) {  // 遍历第i种物品
        // 从v[i]开始遍历容量（容量小于v[i]时，无法选该物品）
        for (ll j = v[i]; j <= k; j++) {
            // 如果“凑出j - v[i]”是可行的，那么加上当前物品v[i]就能凑出j
            if (dp[j - v[i]]) {
                dp[j] = true;
            }
        }
    }

    // 根据dp[k]的结果输出
    if (dp[k]) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }

    return 0;
}