Complete n tasks in d steps by backtracking

Question

I have several task groups, each group is a chain of tasks, groups are independent of each other. Tasks within a group can only be processed in the order that is determined by the chain of that group.

Each task has an identifier and a cost. Tasks are atomic, they can only be completed immediately by investing in them units of time equal to their cost (not solving half the problem). At the beginning of each step, mtime units are available .

I want to check whether it is possible to complete all tasks within a given number of steps d.

Here are some photos to clarify the situation, each task is a 2-tuple (ID, Cost), tasks in chains can be solved only from left to right.

Here is a graphical example of 6 tasks arranged in 3 groups:

Let's say that m = 5(5 units of time are available at each step) and d = 4(we want to check whether all tasks can be completed in 4 steps). Possible soul:

Another possible solution:

An invalid solution would be (it completes all the tasks in 5 steps, we said that the limit is 4):

My question is:

For this:

• tasks that are grouped into groups
• number of time units mavailable at each step
• and a few steps dthat are allowed

determine whether it is possible to solve all the tasks in steps d, if so, print a possible sequence (task identifiers) in which tasks can be solved so that the steps are performed <= d.

My current approach:

. , A ( , , ) B ( A, <= d ​​ , <= d). B , , , ( ), B ( , ). , > d ( ) ( deques , <= d).

PseudoJavaish code:

// 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 ).

Answer 1

B. , " , , <= m - , <= m ". .

, . A .

A 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
• [false, false, true, true] 2 6, m.

, .