4

我有几组任务，每组都是一个任务链，组是相互独立的。组内的任务只能按照该组的链确定的顺序进行处理。

每个任务都有一个 ID 和一个成本。任务是原子的，它们只能通过投入与其成本相等的时间单位一次完成（不可能解决一半的任务）。在每个步骤的开始都有m可用的时间单位。

我想检查是否可以在给定的步骤数内完成所有任务d。

这里有一些图片来说明情况，每个任务都是一个2元组（ID，Cost），链中的任务只能从左到右解决。

这是 6 个任务分为 3 组的图形示例：

6 个任务，3 个组

假设m = 5（每个步骤中有 5 个可用的时间单位）和那个d = 4（我们想检查是否所有任务都可以在 4 个步骤内完成）。一个可能的解决方案是：

4步解决方案

另一种可能的解决方案是：

另一个 4 步解决方案

一个无效的解决方案是（它在 5 个步骤中完成所有任务，我们说限制是 4）：

无效的 5 步解决方案

我的问题：

对于给定：

  • 分组的任务
  • m每一步都有多个可用的时间单位
  • 以及一些d允许的步骤

确定是否可以解决d步骤中的所有任务，如果可以，则输出一个可能的序列（任务 ID），其中可以解决任务以<= d完成步骤。

我目前的做法：

我试图通过回溯找到解决方案。我创建了一个双端队列列表来对组进行建模，然后查看集合 A（在当前步骤中可以解决的所有任务，每个组的最左侧元素）并找到所有子集 B（A 的子集，其总和为成本是<= d并且不能添加其他任务以使成本总和保持不变<= d）。集合 B 的子集代表我在当前步骤中考虑解决的任务，现在每个子集代表一个选择，我对它们中的每一个进行递归调用（以探索每个选择），其中我传递了 B 中没有元素的双端队列列表（我将它们从双端队列中删除，因为从现在开始我认为它们在这个递归分支中解决了）。一旦递归深度达到，递归调用就会停止> d（超出了允许的步骤数）或找到了解决方案（双端队列列表为空，所有任务均已在<= d步骤内解决）。

伪Javaish代码：

// sequence[1] = j means that task 1 is done at step j
// the param steps is used to track the depth of recursion
findValidSequence (ArrayList<Deque> groups, int[] sequence, int steps) {

    if (steps > d)   // stop this branch since it exceeds the step limit d

    if (groups.isEmpty())  // 0 tasks left, a solution is found, output sequence

    Set A = getAllTasksSolvableDuringCurrentStep();

    Set B = determineAllTheOptionsForTheNextStep(A);

    // make a recursive call for each option to check if any of them leads to a valid sequence
    for (each element in B)  
        findValidSequence(groups.remove(B), sequence.setSolvedTasks(B), steps+1);


}

我在尝试正确实施时迷失了方向，您如何看待我的方法，您将如何解决这个问题？

笔记：

这个问题非常普遍，因为许多调度问题（m机器和n优先级受限的作业）可以简化为这样的问题。

4

1 回答 1

3

这是计算的建议B。这是一个很好的观察，它归结为“给定一个整数数组，找到所有子集，其总和为 <= m 并且我们不能从数组中添加任何其他元素使得 <= m 不被违反”。所以我只解决了这个更简单的问题，并相信你会采用适合你情况的解决方案。

正如我在评论中所说，我正在使用递归。每个递归调用都会查看 A 中的一个元素，并尝试使用该元素的解决方案和没有该元素的解决方案。

在对递归方法的每次调用中，我传递Aand m，这些在每次调用中都是相同的。我传递了一个部分解决方案，告诉哪些先前考虑的元素包含在当前正在构建的子集中，以及包含元素的总和只是为了方便。

/**
 * Calculates all subsets of a that have a sum <= capacity
 * and to which one cannot add another element from a without exceeding the capacity.
 * @param a elements to put in sets;
 * even when two elements from a are equal, they are considered distinct
 * @param capacity maximum sum of a returned subset
 * @return collection of subsets of a.
 * Each subset is represented by a boolean array the same length as a
 * where true means that the element in the same index in a is included,
 * false that it is not included.
 */
private static Collection<boolean[]> maximalSubsetsWithinCapacity(int[] a, int capacity) {
    List<boolean[]> b = new ArrayList<>();
    addSubsets(a, capacity, new boolean[0], 0, Integer.MAX_VALUE, b);
    return b;
}

/** add to b all allowed subsets where the the membership for the first members of a is determined by paritalSubset
 * and where remaining capacity is smaller than smallestMemberLeftOut
 */
private static void addSubsets(int[] a, int capacity, boolean[] partialSubset, int sum,
        int smallestMemberLeftOut, List<boolean[]> b) {
    assert sum == IntStream.range(0, partialSubset.length)
            .filter(ix -> partialSubset[ix])
            .map(ix -> a[ix])
            .sum() 
            : Arrays.toString(a) + ' ' + Arrays.toString(partialSubset) + ' ' + sum;
    int remainingCapacity = capacity - sum;
    if (partialSubset.length == a.length) { // done
        // check capacity constraint: if there’s still room for a member of size smallestMemberLeftOut,
        // we have violated the maximality constraint
        if (remainingCapacity < smallestMemberLeftOut) { // OK, no more members could have been added
            b.add(partialSubset);
        }
    } else {
        // try next element from a.
        int nextElement = a[partialSubset.length];
        // i.e., decide whether  should be included.
        // try with and without.

        // is including nextElement a possibility?
        if (nextElement <= remainingCapacity) { // yes
            boolean[] newPartialSubset = Arrays.copyOf(partialSubset, partialSubset.length + 1);
            newPartialSubset[partialSubset.length] = true; // include member
            addSubsets(a, capacity, newPartialSubset, sum + nextElement, smallestMemberLeftOut, b);
        }

        // try leaving nextElement out
        boolean[] newPartialSubset = Arrays.copyOf(partialSubset, partialSubset.length + 1);
        newPartialSubset[partialSubset.length] = false; // exclude member
        int newSmallestMemberLeftOut = smallestMemberLeftOut;
        if (nextElement < smallestMemberLeftOut) {
            newSmallestMemberLeftOut = nextElement;
        }
        addSubsets(a, capacity, newPartialSubset, sum, newSmallestMemberLeftOut, b);
    }

在一些地方有点棘手。我希望我的评论能帮助你度过难关。否则请询问。

让我们试一试：

    int[] a = { 5, 1, 2, 6 };
    Collection<boolean[]> b = maximalSubsetsWithinCapacity(a, 8);
    b.forEach(ba -> System.out.println(Arrays.toString(ba)));

此代码打印：

[true, true, true, false]
[false, true, false, true]
[false, false, true, true]
  • [true, true, true, false]表示 5、1 和 2 的子集。总和为 8，所以这正好符合 8 的容量 ( m)。
  • [false, true, false, true]表示 1 和 6，总和为 7，我们不能加 2，否则我们会超出容量
  • finally[false, false, true, true]表示 2 和 6，也完全符合容量m。

我相信这会耗尽您的限制范围内的可能性。

于 2017-06-20T20:27:50.103 回答