采药-题解（Java代码）

解题思路:用01背包的动态规划解法来写

注意事项:注意输入的转换以及数组的下标问题，为了方便表示把结果的dp数组的第一位置零

参考代码:

import java.util.Scanner;

public class Main {

    public static void main(String[] args){

    Scanner scan = new Scanner(System.in);

    String[] input = scan.nextLine().split(" ");

    int Time = Integer.parseInt(input[0]);

    int Type = Integer.parseInt(input[1]);

    int[] time = new int[Type];

    int[] value = new int[Type];

    for (int i = 0; i < Type; i++) {

    input = scan.nextLine().split(" ");

    time[i] = Integer.parseInt(input[0]);

    value[i] = Integer.parseInt(input[1]);

    }

    scan.close();

    System.out.println(findmed(Time,Type,time,value));

    }//main

    public static int findmed (int T, int type, int[] time, int[] value) {

    int[] dp = new int[T+1];

    for (int i = 1; i < type + 1; i++) {

    for (int j = T; j >= time[i-1]; j--) {

    dp[j] = Math.max(dp[j], dp[j-time[i-1]] + value[i-1]);

    }

    }

    return dp[T];

    }

}//Class Main