csp202209-2

题目：计算机软件能力认证考试系统

01背包问题

#include<bits/stdc++.h>
using namespace std;
int a[35];
int dp[300005];
int main(){
    int n,x;
    cin>>n>>x;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    int mn=9999999;
    for(int i=1;i<=n;i++){
        for(int j=300005;j>=a[i];j--){
            dp[j]=max(dp[j],dp[j-a[i]]+a[i]);
            if(dp[j]>=x){
                mn=min(mn,dp[j]);
            }
        }
    }
    cout<<mn;
}