注意到

本题是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")