#include <bits/stdc++.h> using namespace std; int bag(vector<int> &a, int cap){     int n = a.size() - 1;     vector<vector<int> > DP(n+1, vector<int>(cap+1, 0));     for(int i=1; i<=n; ++i){         for(int j=1; j<=cap; ++j){             if(a[i-1] > j){                 DP[i][j] = DP[i-1][j];             }else{                 DP[i][j] = max(DP[i-1][j], DP[i-1][j-a[i-1]]+a[i-1]);             }         }     }     return DP[n][cap]; } int main(){     int n, t;     cin>>n>>t;     vector<int> a(n, 0);     for(int i=0; i<n; ++i){         cin>>a[i];     }     sort(a.begin(), a.end());     int max = a[n-1];     int res = bag(a, t-1);     cout<<max+res<<endl;     return 0; }
点赞 评论

相关推荐

点赞 评论 收藏
分享

牛客热帖

更多
牛客网
牛客企业服务