正常01背包写法

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int M = sc.nextInt(), N =sc.nextInt();
        int[] W = new int[N];
        int[] C = new int[N];
        for (int i = 0; i < N; i++) {
            W[i] = sc.nextInt();
            C[i] = sc.nextInt();
        }
        int[][] bag = new int[N][M+1];

        for(int i = 0; i < N; i++){
            for (int j = M; j >= 1; j--) {
                if(i == 0){
                    if(j >= W[i]){
                        bag[i][j] = bag[i][j-W[i]] + C[i];
                    }else bag[i][j] = bag[i][j-1];
                }else if(j >= W[i]){
                    bag[i][j] = Math.max(bag[i-1][j],bag[i-1][j-W[i]] + C[i]);
                }else bag[i][j] = Math.max(bag[i-1][j],bag[i][j-1]);
            }
        }
        System.out.println(bag[N-1][M]);



    }
}