多重背包转01背包(java)

public class Main{
    static int N=999999;
    public static void main(String[] args) {
        InputReader in=new InputReader(System.in);
        int[] time=new int[N];
        int[] beauty=new int[N]; 
        int[] dp=new int[N]; 
        int all,n,t,c,p;
        int i,j,len;
        String s1,s2;
        
        s1=in.readString();
        s2=in.readString();
        n=in.nextInt();
        len=0;
        int x1,x2,y1,y2;
        all=s1.indexOf(‘:‘);
        x1=Integer.parseInt(s1.substring(0,all));
        y1=Integer.parseInt(s1.substring(all+1,s1.length()));
        all=s2.indexOf(‘:‘);
        x2=Integer.parseInt(s2.substring(0,all));
        y2=Integer.parseInt(s2.substring(all+1,s2.length()));
        all=x2*60+y2-x1*60-y1;
        
        
        for(i=0;i<n;i++) {
            t=in.nextInt();
            c=in.nextInt();
            p=in.nextInt();
            if(p==0)p=N;
            for(j=1;j<=p;j=j<<1) {
                time[len]=j*t;
                beauty[len++]=j*c;
                p-=j;
            }
            if(p>0) {
                time[len]=p*t;
                beauty[len++]=p*c;
            }
        }//二进制处理
        
        for(i=0;i<len;i++) {
            for(j=all;j>=time[i];j--) {
                dp[j]=Math.max(dp[j],dp[j-time[i]]+beauty[i]);
            }
        }
        System.out.println(dp[all]);
    }
}