publicclassMain{ publicstaticvoidmain(String[] args){ Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int V = sc.nextInt(); int[] dp = newint[V + 1]; for (int i = 1; i <= N; i++) { int vi = sc.nextInt(); int wi = sc.nextInt(); for (int j = V; j >= vi; j--) { dp[j] = Math.max(dp[j], dp[j-vi] + wi); } } System.out.println(dp[V]); } }
publicclassMain{ publicstaticvoidmain(String[] args){ Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int V = sc.nextInt(); int[] v = newint[N + 1]; int[] w = newint[N + 1]; int[] dp = newint[V + 1]; for (int i = 1; i <= N; i++) { v[i] = sc.nextInt(); w[i] = sc.nextInt(); } for (int i = 1;i <= N; i++) { // 这里用正序遍历是可以实现的,01背包需要逆序 for (int j = v[i]; j <= V; j++) { dp[j] = Math.max(dp[j], dp[j - v[i]] + w[i]); } } System.out.println(dp[V]); } }
在优化下输入,便输入边处理 ,最终可以为这样。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
import java.util.Scanner;
publicclassMain{ publicstaticvoidmain(String[] args){ Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int V = sc.nextInt(); int[] dp = newint[V + 1]; for (int i = 1; i <= N; i++) { int v = sc.nextInt(); int w = sc.nextInt(); for (int j = v; j <= V; j++) { dp[j] = Math.max(dp[j],dp[j - v] + w); } } System.out.println(dp[V]); } }
import java.util.*; publicclassMain{ publicstaticvoidmain(String[] args){ Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int V = sc.nextInt(); List<Integer> vi = new ArrayList<>(); List<Integer> wi = new ArrayList<>(); // 将多重背包拆分成01背包 for (int i = 0; i < N; i++) { int v = sc.nextInt(); int w = sc.nextInt(); int s = sc.nextInt(); for (int k = 1; k < s; k *= 2) { vi.add(k * v); wi.add(k * w); s = s - k; } if (s > 0) { vi.add(s * v); wi.add(s * w); } } // 接下来是01背包解法 int[] dp = newint[V + 1]; for (int i = 0; i < vi.size(); i++) { for (int j = V; j >= vi.get(i); j--) { dp[j] = Math.max(dp[j],dp[j - vi.get(i)] + wi.get(i)); } } System.out.println(dp[V]); } }