01背包Java

很像递推

Java样例

import java.util.*;
public class Main {
    static int n,m;
    static int[] v,w;
    static int[][] f;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        v = new int[n+1];
        w = new int[n+1];
        f = new int[n+1][m+1];
        for(int i=1;i<=n;i++) {
            v[i] = sc.nextInt();
            w[i] = sc.nextInt();
        }

        for(int i=1;i<=n;i++) {
            for(int j=0;j<=m;j++) {
                f[i][j] = f[i-1][j];
                if(j>=v[i]) f[i][j]= Math.max(f[i][j], f[i-1][j-v[i]]+w[i]);
            }
        }
        System.out.println(f[n][m]);
    }

}

优化

import java.util.*;
public class Main {
    static int n,m;
    static int[] v,w;
    static int[] f;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        v = new int[n+1];
        w = new int[n+1];
        f = new int[m+1];
        for(int i=1;i<=n;i++) {
            v[i] = sc.nextInt();
            w[i] = sc.nextInt();
        }

        for(int i=1;i<=n;i++) {
            for(int j=m;j>=v[i];j--) {
                f[j]= Math.max(f[j], f[j-v[i]]+w[i]);
            }
        }
        System.out.println(f[m]);
    }

}