采药-题解(Java代码)

import java.util.Scanner;
public class 动态规划问题 {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int max=sc.nextInt();//能够用来采药的时间
        int n=sc.nextInt();//草药个数
        int[]W=new int[n];//摘草药所需的时间
        int[]val=new int[n];//草药的价值
        for (int i = 0; i < n; i++) {
            W[i]=sc.nextInt();
            val[i]=sc.nextInt();
        }
        int[][]v=new int[n+1][max+1];
        for (int i = 1; i < v.length; i++) {
            for (int j = 1; j < v[i].length; j++) {
                if (W[i-1]>j) {
                    v[i][j]=v[i-1][j];
                }else {
                    v[i][j]=Math.max(v[i-1][j], val[i-1]+v[i-1][j-W[i-1]]);
                }
            }
        }
        System.out.println(v[n][max]);
    }
}