采药，采用01背包算法

解题思路:这道题采用01背包算法

注意事项:

参考代码:

public class test61 {
   public static void main(String[] args) {
       Scanner data=new Scanner(System.in);
       int T=data.nextInt();
       int M=data.nextInt();
       int[][] a=new int[M+1][T+1];//构建一个dp数组，用来存放最优解，创建该数组要比正常的大一，因为下面的循环是从1开始的
       int[] t=new int[M+1];//这个数组用来存放采各个药的时间，顺序不能变
       int[] v=new int[M+1];//这个数组用来存取各个药的价值，顺序不能变

//这个循环用来输入
       for (int i=1;i<M+1;i++){
           t[i]=data.nextInt();
           v[i]=data.nextInt();
       }

//这个循环用来计算最优解和存放最优解
       for (int i=1;i<M+1;i++){
           for (int j=0;j<T+1;j++){

//这个if用来比较，当前物品所需时间大于还剩余的时间
               if (t[i]>j){
                   a[i][j]=a[i-1][j];
               }else{
                   a[i][j]=max(a[i-1][j],a[i-1][j-t[i]]+v[i]);
               }
           }
       }

//最优解存放在最大的下标
       System.out.println(a[M][T]);
   }

   public static int max(int i, int b) {
       
       return i>b? i:b;
   }
}