正常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]);



    }
}

通过动态规划算法解决了 0-1 背包问题，通过递归加记忆化搜索的方式，避免了重复计算，提高了效率。

import java.io.*;

public class Main {
    // 创建输入流和输出流
    static StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int[] W;  // 物品的重量数组
    static int[] V;  // 物品的价值数组
    static int m, n;  // 背包的容量和物品的数量
    static int[][] temp = new int[300][500];  // 用于存储中间状态的数组

    public static void main(String[] args) throws Exception {
        m = Int();  // 读入背包的容量
        n = Int();  // 读入物品的数量
        W = new int[n];  // 初始化物品的重量数组
        V = new int[n];  // 初始化物品的价值数组
        // 读入每件物品的重量和价值
        for (int i = 0; i < n; i++) {
            W[i] = Int();
            V[i] = Int();
        }
        // 调用动态规划函数求解背包问题，得到最大价值
        int res = dp(0, m);
        System.out.println(res);  // 输出结果
    }

    // 动态规划函数，采用递归加记忆化搜索的方式
    public static int dp(int cur, int capacity){
        // 递归结束条件：当所有物品都考虑过了或者背包容量为0时，返回0
        if(cur == n || capacity == 0) return 0;
        // 如果之前已经计算过当前状态，直接返回之前的结果
        if(temp[cur][capacity] != 0) return temp[cur][capacity];
        // 不放入当前物品的价值
        int p1 = dp(cur + 1, capacity);
        int p2 = 0;
        // 如果当前物品的重量小于等于背包容量，考虑放入当前物品的情况
        if(capacity - W[cur] >= 0) p2 = V[cur] + dp(cur + 1, capacity - W[cur]);
        // 取不放入和放入当前物品的最大价值作为当前状态的结果
        temp[cur][capacity] = Math.max(p1, p2);
        return temp[cur][capacity];
    }

    // 读取整数的方法
    public static int Int() throws Exception{
        st.nextToken();
        return (int)(st.nval);
    }
}

import java.math.BigInteger;

import java.util.Scanner;

public class Main {

public static void main(String[] args) {

Scanner sc=new Scanner(System.in);

int m=sc.nextInt();

int n=sc.nextInt();

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

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

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

s[i]=sc.nextInt();

v[i]=sc.nextInt(); }

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

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

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

if(s[i]>j)arr[i][j]=arr[i-1][j];

else arr[i][j]=Math.max(arr[i-1][j],arr[i-1][j- s[i]]+v[i]);

}

}

System.out.printf("%d",arr[n][m]);

}

}