本文共 1339 字，大约阅读时间需要 4 分钟。

贪心算法是一种在有序数组中寻找最优解的有效策略。以下是基于贪心算法实现的“独木舟上的旅行2”问题的解决方案。

方法概述

该算法通过以下步骤解决问题：

代码实现

public class 独木舟上的旅行2 {    public static void main(String[] args) {        Scanner sc = new Scanner(System.in);        int k = sc.nextInt();        while (k-- > 0) {            int w = sc.nextInt();            int n = sc.nextInt();            int[] arr = new int[n];            boolean[] flag = new boolean[n];                        for (int i = 0; i < n; i++) {                arr[i] = sc.nextInt();            }            Arrays.sort(arr);                        int count = 0;            for (int i = 0; i < n; i++) {                if (!flag[i]) {                    for (int j = n - 1; j > i; j--) {                        if (!flag[j] && arr[i] + arr[j] <= w) {                            count++;                            flag[j] = true;                            break;                        } else if (j == i + 1) {                            count++;                            break;                        }                    }                }            }            System.out.println(flag[n - 1] ? count : count + 1);        }    }}

代码解释

该算法通过贪心策略确保了在每一步选择最优解，从而在整体上获得最优解。