文章
149
粉丝
0
获赞
481
访问
21.4k
#include<bits/stdc++.h>
using namespace std;
int main() {
int dp[1005][1005] = {0};//只有 0 和 1,0 表示不可以 1 表示可以
int w[1005];
int s,n;
while(cin >> s >> n){
for(int i=1;i<=n;i++){
cin >> w[i];
}
memset(dp,0,sizeof(dp));
dp[0][0] = 1;//前 0 件物品中能拼凑出 0 重量的方案,所以为 1
for(int i=1;i<=n;i++){
for(int j=s;j>=0;j--){
if(dp[i-1][j] == 1) //如果前 i-1 个物品能凑出重量 j
dp[i][j] = 1; //那么前 i 个物品也一定能凑出重量 j(不选第 i 个物品)
if(j - w[i] >= 0 && dp[i - 1][j - w[i]] == 1) //如果前 i-1 个物品能凑出重量 j-w[i]
//条件j - w[i] >= 0 要凑的重量 j 必须大于等于第 i 个物品的重量 w[i]
//如果要选第 i 个物品,重量 j 至少要能容纳这个物品
//如果 j < w[i],即使想选也选不了,因为会超重
dp[i][j] = 1; //那么选上第 i 个物品后,就能凑出重量 j
}
}
if(dp[n][s] == 1)
cout << "YES" << endl;
else
cout << "NO" << endl;
}
return 0;
}
登录后发布评论
暂无评论,来抢沙发