#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; }
点赞 评论

相关推荐

不愿透露姓名的神秘牛友
04-30 11:43
春招失败、父母离婚,好像我的人生一团糟,一年来压力大到常常崩溃。不知道能跟谁聊,朋友其实对我非常好,但是她无意中表达出来的家庭幸福都会刺痛到我……和ai聊天,我的未来在更高处,不在楼下,忍不住爆哭😭
youngfa:害,妹妹,我是一个研究生(很上进很想找到好工作的那种),但去年因为生病回家休养错过了秋招(当时对我的冲击也是非常大的),这学期返校来了也是把论文盲审交了后才开始找工作,现在也是一个offer没有,但我就没有像你一样把这个阶段性的事情绑定到人生上,人生不仅很长,也很广阔,先停下来,放松一下哦。不要被外部环境灌输的思维操控了,好好爱自己!
点赞 评论 收藏
分享
牛客网
牛客企业服务