0-1背包|题解-简单的烦恼

题目：

定时t时间关闭播放音乐，最多能听多长时间的歌？

思路：

找边界，据题意，播放音乐时长超过n越长越好，那么最大边界就是n+max[v[i]]-1。背包问题中的体积和价值在这里都是v[i]。

再按照01背包模板写就可以了。

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
//        第i首歌进来，使得前i-1首歌<=n-1,而第i首歌进来>=n,即dp[i]-v[i]<n
//         总的-不选的>=n, n-不选的<=max(v[i])-1
//         所以实际边界是，n+max[v[i]]-1
        int T=in.nextInt();
        for(int i=0;i<T;i++){
            int n=in.nextInt();
            int t=in.nextInt();
            int [] nums=new int[n+1];
            int max=0;
            for(int j=0;j<n;j++){
                nums[j]=in.nextInt();
                if(nums[j]>max){
                    max=nums[j];
                }
            }
			
            int[] dp=new int[t+max];
            
            for(int a=0;a<=n;++a){
                for(int b=t+max-1;b>=nums[a];b--){
                    dp[b]=Math.max(dp[b],dp[b-nums[a]]+nums[a]);
                }
            }
            System.out.println(dp[t+max-1]);
        }
         
    }
}