注意到

本题是01 背包可行性问题，核心是判断是否存在若干物品，价格之和恰好等于总钱数。

我们采用动态规划求解，定义布尔数组(dp[j])表示能否恰好凑出金额j。

初始状态(dp[0]=1)，表示0元一定可以凑出。 依次遍历每个商品价格，从后向前倒序更新数组，确保每个商品只被选择一次,

若(dp[j])可达且(j+x<=w)，则标记(dp[j+x]=1)。

最终检查dp[w]是否为1，若是则输出 Yes，否则输出 No。

C++

ll n;
int main()
{
    AC;
    int t; cin>>t;
    while(t--)
    {  
        int m; 
        cin>>m>>n;
        vec<ll>a(n+1,0);
        a[0]=1;
        for(int i=0;i<m;++i)
        {
            int  x; cin>>x;
            for(int j=n;j>=0;--j)
                if(a[j]==1&&j+x<=n) 
                    a[x+j]=1;
        }
        if(a[n]==1) cout<<"Yes\n";
        else cout<<"No\n";
    }
    return 0;
}

Python

import sys
input=sys.stdin.readline
t=int(input())
for _ in range(t):
    m,n=map(int,input().split())
    a=[0]*(n+1)
    a[0]=1
    c=list(map(int,input().split()))
    for x in c:
        for j in range(n,-1,-1):
            if a[j]and j+x<=n:a[j+x]=1
    print("Yes"if a[n]else"No")

t = int(input())
for _ in range(t):
    n,w = map(int,input().split())
    lst = list(map(int,input().split()))
    dp = [False]*(w+1)
    dp[0] = True
    for price in lst:
        for j in range(w,price-1,-1):
            dp[j] = dp[j] or dp[j-price]
    print("Yes" if dp[w] else "No")

1.我觉得难理解的点在于dp的布尔值这块吧，本质就是判断是否可以凑出来(先说选的话) 1.1举例子最容易理解了 例如 例子 : n =5,w=5, Price = 2，1，6，2，2 1)第一个商品，价格为2，倒序遍历，即为 j = 5 dp[5] or dp[5-2] = F 2)j = 4,dp[4] = dp[4] or dp[4-2] = F 3)j = 3,dp[3] = dp[3] or dp[1] = F 4)j = 2,dp[2] = dp[2] or dp[0] = T 这里即，凑出0元一定是可行的，所以dp[0]=T,那么之所以减去2，就是我这个2元是一定可以凑出来的，看的是减去2元后的，dp[j-2]是否可以凑出来，如果dp[j-2]是可以凑出来的，那么dp[j]就可以凑出来的 例子2 价格为1 中间省略，直接看下面的就是， dp[3] = dp[3] or [2] =T 同样子，我3元能不能凑出，看的是减去这个物品价格为1元的剩余价值2元可否凑出，凑得出，那么dp[3]就可以凑出来了 综上 理解了这些，这道题就好理解了 下面是全面的考虑

1. 不买这件商品：dp[j] 原来的值 它代表「还没考虑当前这件商品的时候，j 元能不能凑出来」。如果之前就已经能凑出 j 元了，那哪怕不买这件商品，j 元依然是能凑出来的。
2. 买这件商品：dp[j - price] 即：如果 j-price 元能凑出来，那加上这件价格为 price 的商品，刚好就能凑出 j 元。

dp[j] = dp[j] or dp[j - price] 的意思就是： 这两种情况，只要有一个是能凑出来的，那 j 元就可以凑出来。 #例子理解，上述的 买第二个价格为1的物品时，dp[2] = dp[2] or dp[1] = T ,也就是不买当前的物品，这2元，我是凑得出来的