火车运输
双背包问题
f[i][j][k][0] 表示前i个物品,第一个背包容量为j,第二个背包容量为k,且第i件物品考虑到第一个背包的最大价值
f[i][j][k][1] 表示前i个物品,第一个背包容量为j,第二个背包容量为k,且第i件物品考虑到第二个背包的最大价值
状态转移方程:
f[i][j][k][0] = max(f[i - 1][j][k][0], f[i - 1][j - v[i]][k][1] + w[i], f[i - 1][j - v[i]][k][0] + w[i])
第1和4维度都可以优化
1和4优化
import java.util.Scanner;
public class Main {
static final int N = 210, M = 1010;
static int[][] f = new int[M][M];
static int n, m1, m2;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m1 = sc.nextInt();
m2 = sc.nextInt();
for (int i = 1; i <= n; i++) {
int v = sc.nextInt();
for (int j = m1; j >= 0; j--) {
for (int k = m2; k >= 0; k--) {
if (j >= v) {
f[j][k] = Math.max(f[j][k], f[j - v][k] + v);
}
if (k >= v) {
f[j][k] = Math.max(f[j][k], f[j][k - v] + v);
}
}
}
}
System.out.println(f[m1][m2]);
}
}
(第一维度优化)
import java.util.Scanner;
public class Main {
static final int N = 210, M = 1010;
static int[][][] f = new int[M][M][2];
static int[] v = new int[N], w = new int[N];
static int n, m1, m2;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m1 = sc.nextInt();
m2 = sc.nextInt();
for (int i = 1; i <= n; i++) {
v[i] = sc.nextInt();
w[i] = v[i];
}
for (int i = 1; i <= n; i++) {
for (int j = m1; j >= 0; j--) {
for (int k = m2; k >= 0; k--) {
if (j >= v[i]) {
f[j][k][0] = Math.max(f[j][k][0], f[j - v[i]][k][1] + w[i]);
f[j][k][0] = Math.max(f[j][k][0], f[j - v[i]][k][0] + w[i]);
}
if (k >= v[i]) {
f[j][k][1] = Math.max(f[j][k][1], f[j][k - v[i]][0] + w[i]);
f[j][k][1] = Math.max(f[j][k][1], f[j][k - v[i]][1] + w[i]);
}
}
}
}
System.out.println(Math.max(f[m1][m2][0], f[m1][m2][1]));
}
}
另一种滚动数组的优化方式
import java.util.Scanner;
public class Main {
static final int N = 210, M = 1010;
static int[][][][] f = new int[2][M][M][2];
static int[] v = new int[N], w = new int[N];
static int n, m1, m2;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m1 = sc.nextInt();
m2 = sc.nextInt();
for (int i = 1; i <= n; i++) {
v[i] = sc.nextInt();
w[i] = v[i];
}
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= m1; j++) {
for (int k = 0; k <= m2; k++) {
int t1 = i, t2 = i - 1;
t1 &= 1;
t2 &= 1;
int[] a1 = f[t1][j][k];
int[] a2 = f[t2][j][k];
a1[0] = a2[0];
a1[1] = a2[1];
if (j >= v[i]) {
a1[0] = Math.max(a1[0], f[t2][j - v[i]][k][1] + w[i]);
a1[0] = Math.max(a1[0], f[t2][j - v[i]][k][0] + w[i]);
}
if (k >= v[i]) {
a1[1] = Math.max(a1[1], f[t2][j][k - v[i]][0] + w[i]);
a1[1] = Math.max(a1[1], f[t2][j][k - v[i]][1] + w[i]);
}
f[t1][j][k] = a1;
f[t2][j][k] = a2;
}
}
}
System.out.println(Math.max(f[n & 1][m1][m2][0], f[n & 1][m1][m2][1]));
}
}