背包型动态规划

解题思路:

注意事项:

参考代码:

    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        int n=scanner.nextInt();
        int[] dp=new int[n+1];
        int m=scanner.nextInt();
        for(int i=0;i<m;i++){
            int t=scanner.nextInt();
            int val=scanner.nextInt();
            for(int j=n;j>=t;j--){
                dp[j]=Math.max(dp[j],dp[j-t]+val);
            }
        }
        System.out.println(dp[n]);
    }