接金币是经典的街机小游戏：游戏区域内随机掉落金币，玩家控制角色在有限时间内尽可能多地收集金币。每个金币有固定的位置和分值，角色移动速度有限，需要在时间约束内规划最优路径。本文将用 Java 实现基于区间动态规划的收集策略，将问题转化为带时间窗口的路径优化问题，并引入状态压缩技术处理小规模场景的最优解。
一、问题建模与算法设计
1.1 游戏场景抽象
将游戏场景建模为二维平面，每个金币表示为 (x, y, value, appearTime, disappearTime)。角色从起点 (0, 0) 出发，以速度 v 移动，需要在金币的有效时间窗口内到达其位置才能收集。
1.2 区间动态规划思路
当金币按出现时间排序后，问题具有最优子结构：在收集第 i 个金币后，后续的最优策略只与当前位置和时间有关。定义状态 dp[i][j] 为从起点出发，经过时间区间 [0, time_j]，最后收集金币 i 的最大分值。状态转移时需要检查从上一个金币 k 移动到 i 是否满足时间约束。
1.3 状态压缩扩展
当金币数量 n ≤ 20 时，可以使用状态压缩动态规划：用二进制掩码 mask 表示已收集的金币集合，dp[mask][i] 表示已收集 mask 中所有金币且最后停在金币 i 的最大分值。
二、Java 实现
2.1 基础数据结构与工具类
import java.util.*;
/**
* 接金币游戏：金币数据模型
*/
public class Coin {
final int id;
final double x, y; // 位置坐标
final int value; // 分值
final double appearTime; // 出现时间
final double disappearTime; // 消失时间
public Coin(int id, double x, double y, int value, double appear, double disappear) {
this.id = id;
this.x = x;
this.y = y;
this.value = value;
this.appearTime = appear;
this.disappearTime = disappear;
}
/**
* 计算两点之间的欧几里得距离
*/
public static double distance(Coin a, Coin b) {
double dx = a.x - b.x;
double dy = a.y - b.y;
return Math.sqrt(dx * dx + dy * dy);
}
/**
* 计算从起点到该金币的距离
*/
public double distanceFromOrigin() {
return Math.sqrt(x * x + y * y);
}
@Override
public String toString() {
return String.format("Coin[%d](%.1f,%.1f) v=%d [%.1f-%.1f]",
id, x, y, value, appearTime, disappearTime);
}
}
2.2 区间动态规划解法（适用于时间窗口约束）
import java.util.*;
/**
* 接金币：区间动态规划求解最优收集路径
* 适用于金币按时间窗口分布、角色移动速度有限的场景
*/
public class CoinCollectorDP {
private static final double SPEED = 2.0; // 角色移动速度（单位距离/单位时间）
/**
* 基于区间DP的最优收集策略
* 状态：dp[i] 表示以第 i 个金币为最后一个收集目标时的最大分值
* 转移：dp[i] = max(dp[k] + coin[i].value) for all k where canReach(k, i)
*
* 时间复杂度: O(n^2)
* 空间复杂度: O(n)
*/
public static Result solveIntervalDP(List<Coin> coins) {
int n = coins.size();
if (n == 0) return new Result(0, new ArrayList<>());
// 按出现时间排序
coins = new ArrayList<>(coins);
coins.sort(Comparator.comparingDouble(c -> c.appearTime));
// dp[i] = 以第 i 个金币结尾的最大分值
int[] dp = new int[n];
int[] parent = new int[n]; // 记录前驱节点，用于路径重建
Arrays.fill(parent, -1);
for (int i = 0; i < n; i++) {
Coin ci = coins.get(i);
// 检查能否从起点直接到达
double timeToReach = ci.distanceFromOrigin() / SPEED;
if (timeToReach <= ci.disappearTime) {
dp[i] = ci.value;
}
// 尝试从其他金币转移过来
for (int k = 0; k < i; k++) {
Coin ck = coins.get(k);
double travelTime = Coin.distance(ck, ci) / SPEED;
double arrivalTime = ck.appearTime + travelTime;
// 需要满足：到达时间 >= 出现时间 且 <= 消失时间
// 同时 k 必须可达（dp[k] > 0 表示有合法路径到 k）
if (dp[k] > 0 && arrivalTime >= ci.appearTime && arrivalTime <= ci.disappearTime) {
if (dp[k] + ci.value > dp[i]) {
dp[i] = dp[k] + ci.value;
parent[i] = k;
}
}
}
}
// 找到最优终点
int maxValue = 0;
int bestEnd = -1;
for (int i = 0; i < n; i++) {
if (dp[i] > maxValue) {
maxValue = dp[i];
bestEnd = i;
}
}
// 重建路径
List<Coin> path = new ArrayList<>();
int cur = bestEnd;
while (cur != -1) {
path.add(coins.get(cur));
cur = parent[cur];
}
Collections.reverse(path);
return new Result(maxValue, path);
}
/**
* 扩展版本：考虑等待策略（提前到达可以等待金币出现）
*/
public static Result solveWithWaiting(List<Coin> coins) {
int n = coins.size();
if (n == 0) return new Result(0, new ArrayList<>());
coins = new ArrayList<>(coins);
coins.sort(Comparator.comparingDouble(c -> c.appearTime));
int[] dp = new int[n];
int[] parent = new int[n];
Arrays.fill(parent, -1);
for (int i = 0; i < n; i++) {
Coin ci = coins.get(i);
double timeToReach = ci.distanceFromOrigin() / SPEED;
// 即使提前到达，也可以等待金币出现
if (timeToReach <= ci.disappearTime) {
dp[i] = ci.value;
}
for (int k = 0; k < i; k++) {
Coin ck = coins.get(k);
double travelTime = Coin.distance(ck, ci) / SPEED;
// 从 k 出发的时间：max(k的出现时间 + 到达k的时间, 实际出发时间)
// 简化：假设在 k 出现后立即出发
double departureTime = ck.appearTime;
double arrivalTime = departureTime + travelTime;
// 如果提前到达，等待到出现时间即可
double effectiveArrival = Math.max(arrivalTime, ci.appearTime);
if (dp[k] > 0 && effectiveArrival <= ci.disappearTime) {
if (dp[k] + ci.value > dp[i]) {
dp[i] = dp[k] + ci.value;
parent[i] = k;
}
}
}
}
int maxValue = 0, bestEnd = -1;
for (int i = 0; i < n; i++) {
if (dp[i] > maxValue) {
maxValue = dp[i];
bestEnd = i;
}
}
List<Coin> path = new ArrayList<>();
int cur = bestEnd;
while (cur != -1) {
path.add(coins.get(cur));
cur = parent[cur];
}
Collections.reverse(path);
return new Result(maxValue, path);
}
static class Result {
final int maxValue;
final List<Coin> path;
Result(int maxValue, List<Coin> path) {
this.maxValue = maxValue;
this.path = path;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("最大分值: ").append(maxValue).append("\n");
sb.append("收集路径:\n");
for (Coin c : path) {
sb.append(" -> ").append(c).append("\n");
}
return sb.toString();
}
}
public static void main(String[] args) {
// 构建测试场景
List<Coin> coins = Arrays.asList(
new Coin(0, 2, 2, 10, 0, 5),
new Coin(1, 5, 1, 20, 1, 6),
new Coin(2, 3, 5, 15, 2, 7),
new Coin(3, 7, 4, 30, 3, 10),
new Coin(4, 1, 6, 25, 1, 8),
new Coin(5, 8, 2, 10, 5, 12),
new Coin(6, 6, 7, 40, 4, 11)
);
System.out.println("=== 接金币：区间动态规划 ===\n");
System.out.println("金币列表:");
for (Coin c : coins) {
System.out.println(" " + c);
}
System.out.println();
System.out.println("基础版本（不等待）:");
Result result1 = solveIntervalDP(coins);
System.out.println(result1);
System.out.println("扩展版本（允许等待）:");
Result result2 = solveWithWaiting(coins);
System.out.println(result2);
}
}
2.3 状态压缩动态规划（适用于 n ≤ 20 的小规模精确解）
import java.util.*;
/**
* 接金币：状态压缩动态规划
* 当金币数量较少时（n <= 20），使用二进制掩码枚举所有子集
* 保证找到全局最优解
*/
public class CoinCollectorBitmaskDP {
private static final double SPEED = 2.0;
/**
* 状态压缩DP求解
* dp[mask][i] = 已收集 mask 中的金币，最后停在金币 i 的最大分值
*
* 时间复杂度: O(2^n * n^2)
* 空间复杂度: O(2^n * n)
* 适用于 n <= 20 的场景
*/
public static Result solveBitmaskDP(List<Coin> coins) {
int n = coins.size();
if (n == 0) return new Result(0, new ArrayList<>());
if (n > 20) {
throw new IllegalArgumentException("状态压缩DP适用于n<=20的场景，当前n=" + n);
}
int totalMasks = 1 << n;
int[][] dp = new int[totalMasks][n];
int[][] parent = new int[totalMasks][n];
for (int[][] arr : new int[][][]{dp, parent}) {
for (int[] row : arr) {
Arrays.fill(row, -1);
}
}
// 初始化：从起点到每个金币
for (int i = 0; i < n; i++) {
Coin ci = coins.get(i);
double time = ci.distanceFromOrigin() / SPEED;
if (time <= ci.disappearTime) {
dp[1 << i][i] = ci.value;
}
}
// 状态转移
for (int mask = 1; mask < totalMasks; mask++) {
for (int last = 0; last < n; last++) {
if ((mask & (1 << last)) == 0) continue; // last不在mask中
if (dp[mask][last] < 0) continue; // 不可达
Coin lastCoin = coins.get(last);
// 尝试前往下一个金币
for (int next = 0; next < n; next++) {
if ((mask & (1 << next)) != 0) continue; // 已经收集过
Coin nextCoin = coins.get(next);
double travelTime = Coin.distance(lastCoin, nextCoin) / SPEED;
double arrivalTime = lastCoin.appearTime + travelTime;
double effectiveArrival = Math.max(arrivalTime, nextCoin.appearTime);
if (effectiveArrival <= nextCoin.disappearTime) {
int newMask = mask | (1 << next);
int newValue = dp[mask][last] + nextCoin.value;
if (newValue > dp[newMask][next]) {
dp[newMask][next] = newValue;
parent[newMask][next] = last;
}
}
}
}
}
// 查找最优解
int maxValue = 0;
int bestMask = 0, bestLast = -1;
for (int mask = 1; mask < totalMasks; mask++) {
for (int last = 0; last < n; last++) {
if (dp[mask][last] > maxValue) {
maxValue = dp[mask][last];
bestMask = mask;
bestLast = last;
}
}
}
// 重建路径
List<Coin> path = new ArrayList<>();
int mask = bestMask, last = bestLast;
while (last != -1) {
path.add(coins.get(last));
int prev = parent[mask][last];
mask = mask ^ (1 << last);
last = prev;
}
Collections.reverse(path);
return new Result(maxValue, path);
}
static class Result {
final int maxValue;
final List<Coin> path;
Result(int maxValue, List<Coin> path) {
this.maxValue = maxValue;
this.path = path;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("最大分值: ").append(maxValue).append("\n");
sb.append("收集路径:\n");
for (Coin c : path) {
sb.append(" -> ").append(c).append("\n");
}
return sb.toString();
}
}
public static void main(String[] args) {
// 小规模测试（n=10，状态空间 1024）
List<Coin> coins = new ArrayList<>();
Random rand = new Random(42);
for (int i = 0; i < 10; i++) {
coins.add(new Coin(i,
rand.nextDouble() * 10,
rand.nextDouble() * 10,
10 + rand.nextInt(41), // 分值 10-50
rand.nextDouble() * 3, // 出现时间 0-3
5 + rand.nextDouble() * 10 // 消失时间 5-15
));
}
System.out.println("=== 接金币：状态压缩动态规划 ===\n");
System.out.println("金币数量: " + coins.size());
System.out.println("状态空间: 2^" + coins.size() + " = " + (1 << coins.size()));
System.out.println();
long start = System.currentTimeMillis();
Result result = solveBitmaskDP(coins);
long end = System.currentTimeMillis();
System.out.println(result);
System.out.println("计算耗时: " + (end - start) + "ms");
}
}
2.4 贪心启发式策略（大规模近似解）
import java.util.*;
/**
* 接金币：贪心启发式策略
* 当金币数量很大时，使用贪心策略获得近似最优解
* 策略：每次选择"单位时间收益最高"且可达的金币
*/
public class CoinCollectorGreedy {
private static final double SPEED = 2.0;
public static List<Coin> solveGreedy(List<Coin> coins) {
List<Coin> remaining = new ArrayList<>(coins);
List<Coin> path = new ArrayList<>();
double currentX = 0, currentY = 0;
double currentTime = 0;
while (!remaining.isEmpty()) {
Coin best = null;
double bestScore = -1;
for (Coin c : remaining) {
double dist = Math.sqrt((c.x - currentX) * (c.x - currentX)
+ (c.y - currentY) * (c.y - currentY));
double travelTime = dist / SPEED;
double arrivalTime = currentTime + travelTime;
double effectiveArrival = Math.max(arrivalTime, c.appearTime);
if (effectiveArrival > c.disappearTime) continue; // 无法到达
// 评分：分值 / (等待时间 + 移动时间)
double waitTime = Math.max(0, c.appearTime - arrivalTime);
double score = (double) c.value / (travelTime + waitTime + 1);
if (score > bestScore) {
bestScore = score;
best = c;
}
}
if (best == null) break; // 没有可达的金币了
path.add(best);
double dist = Math.sqrt((best.x - currentX) * (best.x - currentX)
+ (best.y - currentY) * (best.y - currentY));
currentTime = Math.max(currentTime + dist / SPEED, best.appearTime);
currentX = best.x;
currentY = best.y;
remaining.remove(best);
}
return path;
}
public static void main(String[] args) {
// 大规模测试
List<Coin> coins = new ArrayList<>();
Random rand = new Random(42);
for (int i = 0; i < 100; i++) {
coins.add(new Coin(i,
rand.nextDouble() * 50,
rand.nextDouble() * 50,
10 + rand.nextInt(91),
rand.nextDouble() * 5,
10 + rand.nextDouble() * 20
));
}
System.out.println("=== 接金币：贪心启发式策略 ===\n");
long start = System.currentTimeMillis();
List<Coin> path = solveGreedy(coins);
long end = System.currentTimeMillis();
int totalValue = path.stream().mapToInt(c -> c.value).sum();
System.out.println("收集金币数: " + path.size());
System.out.println("总分值: " + totalValue);
System.out.println("计算耗时: " + (end - start) + "ms");
}
}
三、复杂度分析
| 算法 | 时间复杂度 | 空间复杂度 | 最优性保证 | 适用规模 |
|---|---|---|---|---|
| 区间DP | O(n²) | O(n) | 最优（单路径） | n ≤ 10⁴ |
| 状态压缩DP | O(2ⁿ × n²) | O(2ⁿ × n) | 全局最优 | n ≤ 20 |
| 贪心启发式 | O(n²) | O(n) | 近似最优 | n ≤ 10⁵ |
四、策略选择指南
- 金币数量 ≤ 20：使用状态压缩DP，保证全局最优
- 金币数量 20~1000，有时间窗口：使用区间DP，考虑时间约束
- 金币数量 > 1000 或实时性要求高：使用贪心启发式，快速获得近似解
- 混合策略：先用贪心快速获得下界，再用局部搜索（如2-opt）改进
五、总结
本文将接金币游戏抽象为带时间窗口的路径优化问题，从区间动态规划、状态压缩精确解到贪心启发式近似解，提供了覆盖不同规模场景的完整算法体系。区间DP通过将时间维度纳入状态设计，优雅地处理了金币出现和消失的时序约束；状态压缩技术虽然指数级复杂，但对于小规模问题能提供无可替代的全局最优保证。在实际游戏开发中，可根据关卡金币密度和性能要求灵活选择策略，或在不同规模间自动切换算法。
