#include <bits/stdc++.h> using namespace std; int main() { int v; cin>>v; while(v--) { int m,t; cin>>m>>t; int n[m+10]; int a[m+10][t+10]; memset(a,0,sizeof(a)); memset(n,0,sizeof(n)); for(int i=1;i<=m;i++) { cin>>n[i]; } sort(n,n+m+1); for(int i=1;i<=m;i++) { if(i==m) { if(a[i-1][t]==t) { a[i][t]=a[i-1][t]-n[1]+n[m]; cout<<a[m][t]<<endl; return 0; } else{ a[i][t]=a[i-1][t]+n[m]; cout<<a[m][t]<<endl; return 0; } } for(int j=0;j<=t;j++) { if(j>=n[i]) { a[i][j]=max(a[i-1][j],a[i-1][j-n[i]]+n[i]); } else a[i][j]=a[i-1][j]; } } } }
全部评论
(1) 回帖