1

我知道大多数人不喜欢为人们编写方法，但我希望有人可以帮助我将我的算法转换为 Java 代码。我希望我的算法很好并且确实有效。

  1. 将给定的整数数组按升序排序。将组限制设置为 15（这意味着组的总和不大于 15）。
  2. 取出排序数组的第一个元素并插入到组（新数组/列表）中，例如。A组。
  3. 取出排序数组的第二个元素并插入，除非它超出组限制。如果超过，则创建一个新的 B 组并插入其中。
  4. 取第三个元素并尝试插入下一个可用组。
  5. 重复直到所有ints 都被检查和分组。

输入：

egArray = [1,3,4,6,6,9,12,14]

输出：

A组：[1,3,4,6]，B组：[6,9]，C组：[12]，D组：[14]

我曾尝试这样做，但失败了，甚至不值得我发布我的代码。:-(

这是我为自学编写的示例数据和算法，因此请尽量减少批评。我真的从人们在过去几个月里写的很多 Stackoverflow 帖子中学到了东西，不幸的是我找不到像这个例子这样的帖子。谢谢。

4

2 回答 2

2

试试这个：

public static void main(String[] arguments) {
    int limit = 15;
    int[] egArray = new int[] { 14, 1, 3, 4, 6, 6, 9, 12 };

    ArrayList<ArrayList<Integer>> a = grouping(limit, egArray);
    System.out.println(a);
}

public static ArrayList<ArrayList<Integer>> grouping(int limit, int[] array) {
    // Sort the input array.
    Arrays.sort(array);
    // Copy the int[] to an ArrayList<Integer>
    ArrayList<Integer> input = new ArrayList<>();
    for (int i = 0; i < array.length; i++) {
        input.add(array[i]);
    }

    // Initialize the groups
    ArrayList<ArrayList<Integer>> groups = new ArrayList<>();
    groups.add(new ArrayList<Integer>());
    // Initialize the sums of the groups, to increase performance (I guess).
    ArrayList<Integer> sums = new ArrayList<>();
    sums.add(0);

    // Iterate through the input array until there is no number
    // left in it (that means we just added all the numbers
    // into our groups array).
    while (!input.isEmpty()) {
        int n = input.get(0); // Store the number to 'n', to shortcut.
        if (n > limit) {
            String msg = "number is greater than the limit; cannot add number";
            throw new IllegalArgumentException(msg);
            // Or whatever to do if the number is larger than the limit.
        }
        boolean match = false;
        // Search the next groups and check if our current
        // number ('n') fits.
        for (int i = 0; i < sums.size(); i++) {
            if (sums.get(i) + n <= limit) {
                // If it fits, then add the number to the group.
                sums.set(i, sums.get(i) + n);
                groups.get(i).add(n);
                match = true;
                break;
            }
        }
        // If 'n' doesn't fit in any group, create a new one.
        if (!match) {
            ArrayList<Integer> e = new ArrayList<>();
            e.add(n);
            groups.add(e);
            sums.add(n);
        }
        // Remove our number.
        input.remove(0);
    }
    return groups;
}

请注意，该方法返回 anArrayList<ArrayList<Integer>>而不是 an int[][]，但效果是相同的。为了检查组的值，只需运行main(String).

于 2012-12-01T22:06:28.713 回答
1

这个方法怎么样？

public static ArrayList group(ArrayList<Integer> arr, Integer groupLimit) {
    ArrayList<ArrayList> result = new ArrayList<ArrayList>();
    ArrayList<Integer> temp = new ArrayList<Integer>();
    for (Integer x : arr) {
        if (sumElements(temp) + x < groupLimit) { 
            temp.add(x);
        } else {
            result.add(temp);
            temp = new ArrayList<Integer>();
            temp.add(x);
        }
    }
    if (temp.size() > 0) {
        result.add(temp);
    }
    return result;
}

public static int sumElements(ArrayList<Integer> arr) {
    Integer result = 0;
    for(Integer x:arr) result += x;
    return result;
}
于 2012-12-01T20:08:50.177 回答