文章
39
粉丝
74
获赞
1
访问
19.0k
#include <stdio.h>
#include <stdlib.h>
int s,n;
int w[1000];
int dp[1000][1000];
int max(int a,int b)
{
if(a>=b)return a;
else return b;
}
int main()
{
while(scanf("%d%d",&s,&n)!=EOF)
{
//dp[i][j]放前i个物品,能不能刚好装下容量为j的物品
for(int i=0; i<n; i++)scanf("%d",&w[i]);
for(int i=0; i<=s; i++)dp[0][i]=0;
dp[0][w[0]]=1;
for(int i=0; i<n; i++)dp[i][0]=1;
for(int i=1; i<n; i++)
{
for(int j=1; j<=s; j++)
{
if(dp[i-1][j]==1)dp[i][j]=1;
else if(dp[i-1][j-w[i]]==1&&j>=w[i])dp[i][j]=1;
else dp[i][j]=0;
}
}
if(dp[n-1][s]==1)printf("YES\n");
else printf("NO\n");
}
return 0;
}
登录后发布评论
暂无评论,来抢沙发