文章

85

粉丝

0

获赞

568

访问

12.6k

头像
小偷的背包 题解:
P1123 中国科学技术大学机试题
发布于2026年3月8日 19:53
阅读数 136

#include <bits/stdc++.h>
using namespace std;
int main() {
    int s;
    cin>>s;
    int n;
    cin>>n;
    int w[n+1];
    for (int i = 1;i <= n;i++) {
        cin>>w[i];
    }
    int dp[n+1][s+1];
    for (int i = 0;i <=n;i++) {
        for (int j = 0;j <= s;j++) {
            dp[i][j] = 0;
        }
    }
    dp[0][0] = 1;
    for (int i = 1;i <= n;i++) {
        for (int j = s;j >0;j--) {
            if (dp[i-1][j] == 1) {
                dp[i][j] = 1;
            }
            if (w[i]<=j&&dp[i-1][j-w[i]]==1) {
                dp[i][j] = 1;
            }
        }
    }
    if (dp[n][s]==1) {
        cout<<"yes!"<<endl;
    }
    else {
        cout<<"no!"<<endl;
    }
}

 

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发