每日算法 — 使用java实现接金币：贪心策略与动态规划最优收集路径

接金币是经典街机游戏的简化版，金币从屏幕上方随机位置掉落，玩家控制一个篮子左右移动来接住尽可能多的金币。本文将用Java实现接金币游戏，并重点讲解两种核心算法：贪心策略用于实时决策篮子移动方向，动态规划用于求解全局最优收集路径。

游戏场景与问题建模

接金币游戏的核心挑战在于：篮子移动速度有限，而金币掉落位置和速度随机。当屏幕同时出现多枚金币时，玩家需要决定优先收集哪一枚。我们将问题抽象为以下数学模型：

• 游戏区域宽度为 W，篮子位于底部 y=0 处，宽度为 basketWidth
• 第 i 枚金币的初始位置为 (xi, yi)，下落速度为 vi
• 篮子水平移动速度为 speed，每次只能向左或向右移动
• 目标是在时间 T 内收集金币总价值最大

贪心策略：局部最优实时决策

贪心策略的核心思想是：每一步都选择当前”性价比”最高的金币进行收集。我们为每枚金币计算一个优先级分数，篮子始终向分数最高的金币移动。

import java.util.*;

/**
 * 接金币游戏 - 贪心策略实现
 * 每帧选择"最易收集"的金币作为目标
 */
public class CoinCollectorGreedy {

    static class Coin {
        double x, y;      // 金币位置
        double speed;     // 下落速度
        int value;        // 金币价值

        Coin(double x, double y, double speed, int value) {
            this.x = x; this.y = y; 
            this.speed = speed; this.value = value;
        }
    }

    private double basketX;       // 篮子中心位置
    private final double basketSpeed = 5.0;  // 篮子移动速度
    private final double width = 800;        // 游戏区域宽度

    /**
     * 贪心策略：为每枚金币计算收集优先级
     * 优先级 = 价值 / (距离 + 预计下落时间)
     * 距离近且价值高的金币优先收集
     */
    public Coin selectTarget(List<Coin> coins) {
        Coin best = null;
        double bestScore = -1;

        for (Coin coin : coins) {
            double distance = Math.abs(coin.x - basketX);
            double timeToFall = coin.y / coin.speed;  // 预计落地时间
            double timeToReach = distance / basketSpeed; // 篮子到达所需时间

            // 如果来不及收集，跳过
            if (timeToReach > timeToFall) continue;

            // 优先级公式：价值越高、距离越近、时间越充裕，分数越高
            double score = coin.value / (distance + timeToFall * 2 + 1);

            if (score > bestScore) {
                bestScore = score;
                best = coin;
            }
        }
        return best;
    }

    /**
     * 模拟一帧游戏逻辑
     */
    public void update(List<Coin> coins) {
        Coin target = selectTarget(coins);
        if (target != null) {
            // 向目标移动
            if (target.x > basketX) {
                basketX = Math.min(basketX + basketSpeed, width);
            } else if (target.x < basketX) {
                basketX = Math.max(basketX - basketSpeed, 0);
            }
        }

        // 更新金币位置，检测碰撞
        Iterator<Coin> it = coins.iterator();
        while (it.hasNext()) {
            Coin c = it.next();
            c.y -= c.speed;
            if (c.y <= 0 && Math.abs(c.x - basketX) < 30) {
                System.out.println("收集金币，价值：" + c.value);
                it.remove();
            } else if (c.y < 0) {
                it.remove(); // 金币落地消失
            }
        }
    }
}

贪心策略的时间复杂度为 O(N) 每帧，其中 N 为当前金币数量。优点是响应速度快，适合实时游戏；缺点是可能陷入局部最优，错过高价值金币组合。

动态规划：全局最优路径规划

当金币的生成序列已知时（如关卡设计），可以用动态规划求解全局最优收集方案。设 dp[i][x] 表示处理完前 i 枚金币、篮子位于位置 x 时的最大价值。

/**
 * 接金币游戏 - 动态规划全局最优解
 * 适用于金币序列预先确定的情况
 */
public class CoinCollectorDP {

    static class CoinEvent {
        int time;      // 金币出现的时间帧
        int x;         // 金币水平位置
        int value;     // 金币价值

        CoinEvent(int time, int x, int value) {
            this.time = time; this.x = x; this.value = value;
        }
    }

    private static final int MAX_POS = 100;  // 位置离散化粒度
    private static final int INF = Integer.MIN_VALUE / 2;

    /**
     * 动态规划求解最优收集路径
     * dp[t][p] = 第t时刻位于位置p时的最大价值
     * 状态转移：dp[t][p] = max(dp[t-1][q] + collect(t,p))，其中 |p-q| <= speed
     */
    public int solve(List<CoinEvent> events, int totalTime, int basketSpeed) {
        // dp[p] 表示当前时刻位于位置p的最大价值
        int[] dp = new int[MAX_POS + 1];
        Arrays.fill(dp, INF);
        dp[50] = 0; // 初始位置在中间

        // 按时间分组的金币事件
        Map<Integer, List<CoinEvent>> timeMap = new HashMap<>();
        for (CoinEvent e : events) {
            timeMap.computeIfAbsent(e.time, k -> new ArrayList<>()).add(e);
        }

        for (int t = 1; t <= totalTime; t++) {
            int[] newDp = new int[MAX_POS + 1];
            Arrays.fill(newDp, INF);

            // 获取当前时刻出现的金币
            List<CoinEvent> currentCoins = timeMap.getOrDefault(t, Collections.emptyList());

            for (int p = 0; p <= MAX_POS; p++) {
                // 枚举上一时刻的位置q，篮子从q移动到p
                for (int q = Math.max(0, p - basketSpeed); 
                     q <= Math.min(MAX_POS, p + basketSpeed); q++) {
                    if (dp[q] == INF) continue;

                    int value = dp[q];
                    // 检查位置p是否有可收集的金币
                    for (CoinEvent coin : currentCoins) {
                        if (coin.x == p) {
                            value += coin.value;
                        }
                    }
                    newDp[p] = Math.max(newDp[p], value);
                }
            }
            dp = newDp;
        }

        // 返回所有位置中的最大值
        return Arrays.stream(dp).max().orElse(0);
    }

    /**
     * 空间优化版本：滚动数组
     * 时间复杂度 O(T * P * S)，空间复杂度 O(P)
     * T=总时间, P=位置数, S=篮子速度
     */
    public int solveOptimized(List<CoinEvent> events, int totalTime, int basketSpeed) {
        int[] dp = new int[MAX_POS + 1];
        Arrays.fill(dp, INF);
        dp[50] = 0;

        Map<Integer, List<CoinEvent>> timeMap = new HashMap<>();
        for (CoinEvent e : events) {
            timeMap.computeIfAbsent(e.time, k -> new ArrayList<>()).add(e);
        }

        for (int t = 1; t <= totalTime; t++) {
            int[] newDp = new int[MAX_POS + 1];
            Arrays.fill(newDp, INF);
            List<CoinEvent> coins = timeMap.getOrDefault(t, Collections.emptyList());

            for (int p = 0; p <= MAX_POS; p++) {
                int maxPrev = INF;
                for (int q = Math.max(0, p - basketSpeed); 
                     q <= Math.min(MAX_POS, p + basketSpeed); q++) {
                    maxPrev = Math.max(maxPrev, dp[q]);
                }
                if (maxPrev == INF) continue;

                int collect = 0;
                for (CoinEvent c : coins) {
                    if (c.x == p) collect += c.value;
                }
                newDp[p] = maxPrev + collect;
            }
            dp = newDp;
        }

        return Arrays.stream(dp).max().orElse(0);
    }
}

完整可运行项目

import javax.swing.*;
import java.awt.*;
import java.awt.event.*;
import java.util.*;
import java.util.List;

/**
 * 接金币游戏完整实现
 * 结合贪心策略与动态规划分析
 */
public class CoinCollectorGame extends JPanel implements ActionListener {

    private static final int WIDTH = 800;
    private static final int HEIGHT = 600;
    private static final int BASKET_WIDTH = 60;
    private static final int BASKET_SPEED = 8;

    private double basketX = WIDTH / 2.0;
    private List<Coin> coins = new ArrayList<>();
    private int score = 0;
    private int frame = 0;
    private Timer timer;
    private Random rand = new Random();

    static class Coin {
        double x, y;
        int value;
        Color color;

        Coin(double x, double y, int value) {
            this.x = x; this.y = y; this.value = value;
            this.color = value >= 5 ? Color.RED : (value >= 3 ? Color.YELLOW : Color.GREEN);
        }
    }

    public CoinCollectorGame() {
        setPreferredSize(new Dimension(WIDTH, HEIGHT));
        setBackground(Color.BLACK);
        timer = new Timer(30, this); // 约33 FPS

        addKeyListener(new KeyAdapter() {
            @Override
            public void keyPressed(KeyEvent e) {
                switch (e.getKeyCode()) {
                    case KeyEvent.VK_LEFT -> basketX = Math.max(BASKET_WIDTH/2, basketX - BASKET_SPEED * 2);
                    case KeyEvent.VK_RIGHT -> basketX = Math.min(WIDTH - BASKET_WIDTH/2, basketX + BASKET_SPEED * 2);
                }
            }
        });
        setFocusable(true);
    }

    /**
     * AI自动控制：贪心策略实现
     */
    private void aiMove() {
        Coin best = null;
        double bestScore = -1;

        for (Coin c : coins) {
            double dist = Math.abs(c.x - basketX);
            double timeLeft = c.y / 3.0; // 假设下落速度为3
            double timeNeed = dist / BASKET_SPEED;

            if (timeNeed > timeLeft) continue;

            double score = c.value / (dist + timeLeft + 1);
            if (score > bestScore) {
                bestScore = score;
                best = c;
            }
        }

        if (best != null) {
            if (best.x > basketX) basketX = Math.min(WIDTH - BASKET_WIDTH/2, basketX + BASKET_SPEED);
            else if (best.x < basketX) basketX = Math.max(BASKET_WIDTH/2, basketX - BASKET_SPEED);
        }
    }

    @Override
    public void actionPerformed(ActionEvent e) {
        frame++;

        // 每30帧生成一枚金币
        if (frame % 30 == 0) {
            int value = rand.nextInt(5) + 1;
            coins.add(new Coin(rand.nextInt(WIDTH - 40) + 20, 30, value));
        }

        // AI自动移动（可替换为键盘控制）
        aiMove();

        // 更新金币位置并检测碰撞
        Iterator<Coin> it = coins.iterator();
        while (it.hasNext()) {
            Coin c = it.next();
            c.y += 3; // 下落速度

            // 碰撞检测
            if (c.y >= HEIGHT - 40 && Math.abs(c.x - basketX) < BASKET_WIDTH / 2 + 15) {
                score += c.value;
                it.remove();
            } else if (c.y > HEIGHT) {
                it.remove(); // 漏接
            }
        }

        repaint();
    }

    @Override
    protected void paintComponent(Graphics g) {
        super.paintComponent(g);

        // 绘制金币
        for (Coin c : coins) {
            g.setColor(c.color);
            g.fillOval((int)c.x - 15, (int)c.y - 15, 30, 30);
            g.setColor(Color.WHITE);
            g.drawString(String.valueOf(c.value), (int)c.x - 5, (int)c.y + 5);
        }

        // 绘制篮子
        g.setColor(Color.CYAN);
        g.fillRect((int)basketX - BASKET_WIDTH/2, HEIGHT - 40, BASKET_WIDTH, 20);

        // 绘制分数
        g.setColor(Color.WHITE);
        g.setFont(new Font("Arial", Font.BOLD, 20));
        g.drawString("Score: " + score, 20, 30);
        g.drawString("Coins: " + coins.size(), 20, 55);
    }

    public void start() { timer.start(); }

    public static void main(String[] args) {
        SwingUtilities.invokeLater(() -> {
            JFrame frame = new JFrame("接金币 - 贪心策略");
            CoinCollectorGame game = new CoinCollectorGame();
            frame.add(game);
            frame.pack();
            frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
            frame.setVisible(true);
            game.start();
        });
    }
}

算法复杂度分析

贪心策略适合在线游戏场景，动态规划适合离线最优路径计算。实际游戏中可以将两者结合：用动态规划预计算理论最优值，用贪心策略作为实时近似解。

扩展思考

1. 多篮子协作：多个篮子如何分配金币，可建模为二分图匹配问题
2. 带障碍物的接金币：引入障碍物后需要用BFS/寻路算法计算可达性
3. 价值随时间衰减：金币价值随下落递减，贪心优先级公式需要动态调整权重