朴素

import java.io.*;

class Main {
    public static void main(String[] args) throws IOException {
        InputStreamReader isr = new InputStreamReader(System.in);
        BufferedReader in = new BufferedReader(isr);
        String[] strs = in.readLine().split(" ");
        int N = Integer.parseInt(strs[0]);
        int V = Integer.parseInt(strs[1]);
        int[] v = new int[N+1];
        int[] w = new int[N+1];
        for (int i = 1; i<=N; i++) {
            strs = in.readLine().split(" ");
            v[i] = Integer.parseInt(strs[0]);
            w[i] = Integer.parseInt(strs[1]);
        }
        in.close();
        isr.close();

        OutputStreamWriter osw = new OutputStreamWriter(System.out);
        BufferedWriter out = new BufferedWriter(osw);

        int[][] f = new int[N+1][V+1];
        for (int i = 1; i <= N; i++) 
            for (int j = 1; j <= V; j++)
                for (int k = 0; k*v[i] <= j; k++)
                    f[i][j] = Math.max(f[i-1][j - k*v[i]]+k*w[i], f[i][j]);

        out.write(f[N][V]+"");
        out.flush();
        out.close();
        osw.close();
    }
}

时间优化

import java.io.*;

class Main {
    public static void main(String[] args) throws IOException {
        InputStreamReader isr = new InputStreamReader(System.in);
        BufferedReader in = new BufferedReader(isr);
        String[] strs = in.readLine().split(" ");
        int N = Integer.parseInt(strs[0]);
        int V = Integer.parseInt(strs[1]);
        int[] v = new int[N+1];
        int[] w = new int[N+1];
        for (int i = 1; i<=N; i++) {
            strs = in.readLine().split(" ");
            v[i] = Integer.parseInt(strs[0]);
            w[i] = Integer.parseInt(strs[1]);
        }
        in.close();
        isr.close();

        OutputStreamWriter osw = new OutputStreamWriter(System.out);
        BufferedWriter out = new BufferedWriter(osw);

        int[][] f = new int[N+1][V+1];
        for (int i = 1; i <= N; i++) 
            for (int j = 1; j <= V; j++) {
                f[i][j] = f[i-1][j];
                if (j >= v[i]) f[i][j] = Math.max(f[i-1][j],f[i][j-v[i]]+w[i]);
            }
        out.write(f[N][V]+"");
        out.flush();
        out.close();
        osw.close();
    }
}

空间优化

import java.io.*;

class Main {
    public static void main(String[] args) throws IOException {
        InputStreamReader isr = new InputStreamReader(System.in);
        BufferedReader in = new BufferedReader(isr);
        String[] strs = in.readLine().split(" ");
        int N = Integer.parseInt(strs[0]);
        int V = Integer.parseInt(strs[1]);
        int[] v = new int[N+1];
        int[] w = new int[N+1];
        for (int i = 1; i<=N; i++) {
            strs = in.readLine().split(" ");
            v[i] = Integer.parseInt(strs[0]);
            w[i] = Integer.parseInt(strs[1]);
        }
        in.close();
        isr.close();

        OutputStreamWriter osw = new OutputStreamWriter(System.out);
        BufferedWriter out = new BufferedWriter(osw);

        //int[][] f = new int[N+1][V+1];
        int[] f = new int[V+1];
        for (int i = 1; i <= N; i++) 
            for (int j = v[i]; j <= V; j++) {
                //f[i][j] = f[i-1][j];
                //if (j >= v[i]) f[i][j] = Math.max(f[i-1][j],f[i][j-v[i]]+w[i]);
                f[j] = Math.max(f[j],f[j-v[i]]+w[i]);
            }
        out.write(f[V]+"");
        out.flush();
        out.close();
        osw.close();
    }
}