01背包 Java

① 记忆化搜索解法：

import java.util.*;
import java.io.*;public class Main {static int n, m;static int[] v, w;static int[][] memory; // 记忆化数组public static void main(String[] args) throws Exception {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));StringTokenizer st = new StringTokenizer(br.readLine());n = Integer.parseInt(st.nextToken());m = Integer.parseInt(st.nextToken());v = new int[n + 1];w = new int[n + 1];memory = new int[n + 1][m + 1];for (int i = 1; i <= n; i++) {st = new StringTokenizer(br.readLine());v[i] = Integer.parseInt(st.nextToken());w[i] = Integer.parseInt(st.nextToken());}System.out.println(dfs(1, 0));}static int dfs(int i, int vSum) {if (i > n) return 0;if (memory[i][vSum] != 0) return memory[i][vSum]; // 直接返回存储的值，跳过重复计算int reject = dfs(i + 1, vSum); // 左分支，不选当前物品int accept = 0; // 右分支，选中当前物品if (vSum + v[i] <= m)accept = dfs(i + 1, vSum + v[i]) + w[i]; // 要加上物品价值return memory[i][vSum] = Math.max(reject, accept); // 存储当前的值}
}

② dp解法（更优化）：

不能选(背包空间不足)：继承前面，即dp[i - 1][j]。

能选(背包容量足够)：获得该层价值w[i]，同时失去对应背包容量v[i]，然后获得选与不选其中价值更大的一个。

import java.util.*;
import java.io.*;public class Main {public static void main(String[] args) throws Exception {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));StringTokenizer st = new StringTokenizer(br.readLine());int n = Integer.parseInt(st.nextToken());int m = Integer.parseInt(st.nextToken());int[] v = new int[1005];int[] w = new int[1005];int[][] dp = new int[1005][1005];for (int i = 1; i <= n; i++) {st = new StringTokenizer(br.readLine());v[i] = Integer.parseInt(st.nextToken());w[i] = Integer.parseInt(st.nextToken());}for (int i = 1; i <= n; i++) {for (int j = 0; j <= m; j++) {if (j < v[i]) dp[i][j] = dp[i - 1][j];else dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i]);}}System.out.println(dp[n][m]);}
}

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~