题解 | 01背包前置题

#include<bits/stdc++.h>
using namespace std;

using ui=unsigned int;
using ll=long long;
using ull=unsigned long long;
using i128=__int128_t;
using u128=__uint128_t;
using ld=long double;

void solve()
{//我们令dp[i][j]为对于前i个物品 能否取到j 能为1 否为0
//我们需要取到k 所以j的最大值设置成k即可
//当dp[i-1][j]=1时 代表前i-1个数已经可以取到j
//所以dp[i][j]只需要不取 就可以保持j 故dp[i][j]=1;
//如果在加上j+a[i-1]<=k的限制 那么dp[i][j+a[i-1]]=1 因为此时我们选择取当前物品
//最后从1判断到n 看看有没有哪个dp[i][k]=1 有即为Yes 反之则No
	int n,k;
	cin >> n >> k;
	vector<int>a(n,0);
	vector<vector<int>>dp(n+1,vector<int>(k+1,0));
	for(int i=0;i<n;i++) cin >> a[i];
	dp[0][0]=1;
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<=k;j++)
		{
			if(dp[i-1][j]==1) dp[i][j]=1;
			if(dp[i-1][j]==1&&j+a[i-1]<=k) dp[i][j+a[i-1]]=1;
		}
	}
	for(int i=0;i<=n;i++)
	{
		if(dp[i][k]==1)
		{
			cout << "Yes";
			return;
		}
	}
	cout << "No";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int t=1;
	//cin >> t;

	while(t--)
	{
		solve();
	}
	return 0;
}