题解 | 01背包前置题

使用01背包dp思路解决。

目的是找出是否能有一个结果总价值为k，暴力枚举复杂度太大。

不妨将问题转变为 总价值为k是否可以被凑出来？

建立一个dp数组，范围0到k+1，初始化false，dp[i]表示价值i是否可以被凑出来。

dp[0] 置 true，当我们什么物品都不选，价值为0。

从前向后遍历：

j是目标价值，p是当前物品价值，j-p表示"如果我们选择当前物品，还需要凑出多少价值"。

对于每一个物品，如果我们能用之前的物品凑出 j-p，那么再加上当前的物品（价值 p），就能凑出 j：

dp[i] 表示能否拼凑出价值i。

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n,k;
    cin>>n>>k;
    vector<int> v(n+1);
    vector<bool> dp(k+1,false);
    dp[0]=true;
    for(int i=1;i<=n;++i) cin>>v[i];
    for(int i=1;i<=n;++i){
        int p = v[i];
        for(int j=k;j>=p;j--){
            if(dp[j-p]) dp[j]=true;
        }
    }
    cout<<(dp[k]?"Yes":"No");
}