文章

0

粉丝

0

获赞

0

访问

180

头像
1035背包问题,高分篇的答案,为什么编译器通不过但是oj可以
择校分析
发布于2021年2月22日 21:30
阅读数 180

#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;
}

 



登录后发布评论

暂无评论,来抢沙发