public static void main(String[] args){ Scanner sc = new Scanner(System.in); int T = sc.nextInt(); int ans=0; for(int i=0;i<T;i++){ int n = sc.nextInt();//歌单中歌曲的数目 int t = sc.nextInt();//定时t时间后关闭 int[] ml = new int[n];//每首歌曲的时间长度 for(int j=0;j<n;j++){ ml[j] = sc.nextInt(); } Arrays.sort(ml); //背包问题:n-1个物品,承重为t-1,最多能带走多重的物品 ans = maxMusicLength(n-1,t-1,ml); //最长的一首歌最后一分钟听,剩下t-1分钟转化为背包问题 System.out.println(ans+ml[n-1]); } } public static int maxMusicLength(int n,int t,int[] ml){ int[] dp = new int[t+1]; // dp[j] 表示 前 i 首歌 歌曲长度为 j 的最多时间 for(int i = 0; i < n; ++i){ for(int j = t; j >= 0; --j){ if(j >= ml[i]) dp[j] = Math.max(dp[j], dp[j-ml[i]]+ml[i]); } } return dp[t]; }