文章

94

粉丝

0

获赞

522

访问

16.4k

头像
简单背包问题 题解:c++
P1035
发布于2026年3月6日 17:45
阅读数 69

#include <bits/stdc++.h>
using namespace std;
  
int dp[1008][1008];
int w[1008];
int main(){
    int n,s;
    while(cin >> s >> n){
        for(int i = 1; i <= n ; i++) cin >> w[i];
        memset(dp,0,sizeof(dp));
        dp[0][0] = 1;
        for(int i = 1; i <= n; i++){
            for(int j = 0;j<=s;j++){
                if(dp[i-1][j] == 1) dp[i][j] = 1;
                if(j>=w[i] && dp[i-1][j-w[i]] == 1) dp[i][j] = 1;
            }
        }
        if(dp[n][s] == 1) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
    return 0;
}

...
登录查看完整内容


登录后发布评论

暂无评论,来抢沙发