蓝桥杯算法提高VIP-01背包

解题思路:

注意事项:

参考代码:

        Scanner sc = new Scanner(System.in);

        int m=sc.nextInt();

        int n=sc.nextInt();

        int[][] wi=new int[n+1][2];

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

            wi[i][0]=sc.nextInt();///重量

            wi[i][1]=sc.nextInt();//质量

        }

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

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

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

                if (wi[i][0]>j) {

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

                }else {            

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

                }

            }

        }

        System.out.println("max="+dp[n][m]);