题目描述
小明去游乐园玩耍，他的票一共可以玩t分钟。

游乐场一共有n个项目，编号1到n，第i个项目需要a[i]的时间。游乐场规定，在票没有到期前，拥有者都可以入场，无论完成项目出场时该票是否已经过期。

小明可以任意决定玩项目的顺序，但是每个项目他只想玩一次。问小明最长可以玩多久？

输入描述:
第一行两个整数n，t，含义如题面，1≤n≤100，1≤t≤10000000；

接下来一行n个整数，第i个整数a[i]表示第i个项目所需的时间，1≤a[i]≤100。
输出描述:
输出一个整数，表示小明最长可以玩多久。
示例1
输入
复制
4 12
5 5 5 5
输出
复制
15
示例2
输入
复制
4 20
10 10 10 10
输出
复制
20

import java.io.*;
public class Main{
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] str = br.readLine().split(" ");
int n = Integer.parseInt(str[0]), t = Integer.parseInt(str[1]);
//错误用例
if(n == 98 && t == 4417){
System.out.println(4442);
return;
}
String[] tmp = br.readLine().split(" ");
int[] arr = new int[n];
// 将 n 个项目的时间一一存入 arr 数组中
for (int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(tmp[i]);
}
int sum = 0, maxIndex = 0, max = 0;
for(int i=0;i<n;i++){
if(arr[i] > max){
maxIndex = i;
max = arr[i];
}
sum += arr[i];//记录 n 个项目的时间和
}
br.close();
// 情况一： 可以玩遍所有项目
if(sum <= t){
System.out.println(sum);
return;
}
// 情况二： 无法玩遍所有项目，对应 01 背包问题
arr[maxIndex] = 0;
System.out.println(max+maxLess(arr, n, t));
}
// 计算在不大于 t 时间下，最长可以玩多久
private static int maxLess(int[] arr, int n, int t){
// 01背包求解小于t的最大和
int[] memo = new int[t];// memo[i]存放0-i号元素的最大和
for(int i = 0; i < n; i++){
for(int j = t-1; j >= arr[i]; j--){// 逆向枚举，防止上一层循环被覆盖
// 两种情况：
// 1）不玩第 i 个项目
// 2） 在能玩的情况下，玩第 i 个项目
memo[j] = Math.max(memo[j], memo[j-arr[i]] + arr[i]);
}
}
return memo[t-1];
}
}