文章目录

• 1. 问题
• 2.状态和边界条件
• 3. 递推式

1. 问题

有N件物品和一个容积为M的背包
第i件物品的体积是w[i], 价值是d[i]
求解将哪些物品装入背包可以使价值总量和最大
每种物品只有一件，可以选择放或者不放
(N <= 3500, M <= 13000)

2.状态和边界条件

用F[i][j]表示取前i种物品，使他们总体积不超过j的最优取法得到的价值总和。
要求F[N][M]
边界：

if(w[1] <= j)
	F[1][j] = d[1];
else 
	F[1][j] = 0;

3. 递推式

用F[i][j]表示取前i种物品，使他们总体积不超过j的最优取法取得的价值总和
递推：

// 取或者不取第i中物品，两者选优
F[i][j] = max(F[i-1][j],F[i-1][j-w[i]]+d[i])

本题如果用记忆型递归，需要一个很大的二维数组，会超内存。
注意到这个二维数组的下一行的值，只用到了上一行的正上方及左边的值，因此可以使用滚动数组的思想，只要一行即可。

二维数组会超内存

public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskPoj3624 solver = new TaskPoj3624();
        solver.solve(1, in, out);
        out.close();
    }
    static class TaskPoj3624 {
        public void solve(int testNumber, Scanner in, PrintWriter out) {
            int n = in.nextInt();
            int m = in.nextInt();
            int w[] = new int[n + 1];
            int d[] = new int[n + 1];
            for (int i = 1; i <= n; i++) {
                w[i] = in.nextInt();
                d[i] = in.nextInt();
            }

            int dp[][] = new int[n + 1][m + 1];
            for (int i = 1; i <= n; i++)
                dp[i][0] = 0;
            for (int i = 1; i <= m; i++) {
                if (w[1] >= i) {
                    dp[1][i] = d[i];
                } else {
                    dp[1][i] = 0;
                }
            }
            for (int i = 2; i <= n; i++) {
                for (int j = 1; j <= m; j++) {
                    dp[i][j] = dp[i - 1][j];
                    if (j >= w[i]) {
                        dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w[i]] + d[i]);
                    }
                }
            }
            out.println(dp[n][m]);
        }

    }
}

使用一维数组
从右向左递推，不会覆盖上一层仍需要使用的数据

public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskPoj3624 solver = new TaskPoj3624();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskPoj3624 {
        public void solve(int testNumber, Scanner in, PrintWriter out) {
            int n = in.nextInt();
            int m = in.nextInt();
            int w[] = new int[n + 1];
            int d[] = new int[n + 1];
            for (int i = 1; i <= n; i++) {
                w[i] = in.nextInt();
                d[i] = in.nextInt();
            }

            int dp[] = new int[m + 1];
            for (int j = 0; j <= m; j++) {
                if (j >= w[1]) {
                    dp[j] = d[1];
                } else {
                    dp[j] = 0;
                }
            }
            for (int i = 2; i <= n; i++) {
                for (int j = m; j >= 1; j--) {
                    if (j >= w[i]) {
                        dp[j] = Math.max(dp[j], dp[j - w[i]] + d[i]);
                    }
                }
            }
            out.println(dp[m]);
        }

    }
}