
初步思考
为什么不能用一维dp[i]表示“进攻第 i 个星球的最少能量”?
因为没有记录进攻过哪些星球,路线很混乱,而且可能一直在同一个星球上
因此需要定义二维状态压缩DP,定义 dp[mask][u] :mask是二进制状态,表示已进攻的星球集合,u表示当前在星球u,dp数组的值表示从任意走过的路线到此时u的最小能量。
状态压缩:二进制状态是什么意思?
即用二进制数表示 “已经进攻过哪些星球”
n 个星球,每个星球对应二进制的一位:
- 第 0 位为 1:表示星球 0 已经被进攻
- 第 1 位为 1:表示星球 1 已经被进攻
- …
- 第 n-1 位为 1:表示星球 n-1 已经被进攻
所有可能的状态总数就是 2^n 种(每个星球都有 “已进攻 / 未进攻” 两种状态),所以数组长度设为 1 << n
<< 在Java中是左移运算符,表示把数字的二进制位向左移动 n 位,右边补 0。
数学上等价于:1 << n = 2^n(2 的 n 次方)
因此创建dp数组: dp=new double[ 1<<n ][ n ] ;
举个例子,当 n=3 时:
- 1 << 3 = 8,所以第一维长度是 8
- 状态 001(十进制 1):只进攻了星球 0
- 状态 011(十进制 3):进攻了星球 0 和星球 1
- 状态 111(十进制 7):所有星球都进攻完毕
完整理解 dp[mask][u]
结合起来,dp[mask][u] 的含义是:
已经进攻过的星球集合为 mask(二进制表示),当前飞船停在星球 u 时,所消耗的最少能量。
比如 dp[0b101][2](十进制 mask=5,u=2):
- 二进制 101 表示星球 0 和星球 2 已经被进攻
- 当前飞船在星球 2
- 值就是 “按这个顺序进攻,最终停在星球 2 时的最少能量”
带权旅行商问题
- 状态:dp[mask][u] 表示已经访问过的星球集合为 mask,当前在星球 u 时的最小能量消耗。
- 初始化:dp[1 << u][u] = 0(从 u 出发,初始能量为 0)。
- 转移:
dp[mask | (1 << v)][v] = min(
dp[mask | (1 << v)][v],
dp[mask][u] + 距离(u, v) * w[v]
)
- 答案:所有 dp[(1<<n)-1][u] 的最小值。
Java完整代码:
import java.util.*;
public class Main {
static int n;
static int[] x, y, z, w;
// dp[mask][u] 表示状态mask,当前在u点的最小能量
static double[][] dp;
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
n = scan.nextInt();
x = new int[n];
y = new int[n];
z = new int[n];
w = new int[n];
for (int i = 0; i < n; i++) {
x[i] = scan.nextInt();
y[i] = scan.nextInt();
z[i] = scan.nextInt();
w[i] = scan.nextInt();
}
scan.close();
// 状态压缩DP初始化
int fullMask = (1 << n) – 1;
dp = new double[1 << n][n];
for (double[] row : dp) {
Arrays.fill(row, Double.POSITIVE_INFINITY);
}
// 起点:只访问自己,能量为0
for (int i = 0; i < n; i++) {
dp[1 << i][i] = 0.0;
}
// 遍历所有状态
for (int mask = 0; mask < (1 << n); mask++) {
// 遍历当前在哪个星球u
for (int u = 0; u < n; u++) {
if ((mask & (1 << u)) == 0 || dp[mask][u] == Double.POSITIVE_INFINITY) {
continue;
}
// 尝试走到下一个未访问的星球v
for (int v = 0; v < n; v++) {
if ((mask & (1 << v)) != 0) continue;
// 计算u到v的距离
double dist = Math.sqrt(
(x[u] – x[v]) * 1.0 * (x[u] – x[v]) +
(y[u] – y[v]) * 1.0 * (y[u] – y[v]) +
(z[u] – z[v]) * 1.0 * (z[u] – z[v])
);
double cost = dist * w[v];
int newMask = mask | (1 << v);
dp[newMask][v] = Math.min(dp[newMask][v], dp[mask][u] + cost);
}
}
}
// 所有星球都访问完,取最小值
double ans = Double.POSITIVE_INFINITY;
for (int i = 0; i < n; i++) {
ans = Math.min(ans, dp[fullMask][i]);
}
// 保留两位小数输出
System.out.printf("%.2f\\n", ans);
}
}

![P11246 [GESP202409 六级] 小杨和整数拆分-171主机测评](https://www.171host.com/wp-content/uploads/2026/11/20261108100631-6af049a75855c-220x150.png)
![打卡信奥刷题(3678)用C++实现信奥题 P12274 [蓝桥杯 2024 国 Python B] 设计-171主机测评](https://www.171host.com/wp-content/uploads/2026/11/20261108053830-6af00ad6bdf8d-220x150.png)

