文章
1
粉丝
371
获赞
0
访问
8.9k
#include <stdio.h>
#include <string.h>
int main() {
int dp[1005][1005] = {0};//只有0 和1 0 表示不可以1 表示可以
int w[1005];
int s, n;
while (scanf("%d %d", &s, &n) != EOF) {
int i, j;
for (i = 1; i <= n; i++) {
scanf("%d", &w[i]);
}
memset(dp, 0, sizeof(dp));
dp[0][0] = 1;//前0 件物品中能拼凑出0 重量的方案,所以为1
for (i = 1; i <= n; i++) {
for (j = s; j >= 0; j--) {
if (dp[i - 1][j] == 1) dp[i][j] = 1;
if (j - w[i] >= 0 && dp[i - 1][j - w[i]] == 1) dp[i][j] = 1;
}
}
if (dp[n][s] == 1) printf("YES\n");
else printf("NO\n");
}
return 0;
}
登录后发布评论
暂无评论,来抢沙发