典中典---抽象背包

解题思路:

注意事项:

参考代码:

import java.util.*;

public class Main {

public static void main(String[] args) throws Exception {

Scanner scanner=new Scanner(System.in);

int n=scanner.nextInt();

int x=scanner.nextInt();

int []arr=new int[n+1];

int []brr=new int[x+1];

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

        arr[i]=scanner.nextInt();

        brr[i]=scanner.nextInt();

}

int [][]dp=new int [x+1][n+1];

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

        for(int j=1;j<n+1;j++) {

        if(arr[i]>j) {

        dp[i][j]=dp[i-1][j];

        }else {

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

        }

        }

}

System.out.println(dp[x][n]);

}

}