Algorithms and Data Structures for Programming Contests

Brute Force Algorithms (Cont'd)

Regroup

High-level solution?

1. generate all possible subsets of blocks
2. initialize m to ∞
3. for each subset:
   • if the sum of heights in the subset is equal to H, then set m = minimum(m, size of the subset)
4. if m = ∞, output 0; else, output m

Difficulty?

• The only complicated part is how to generate every possible subset of blocks.

High-level solution: use recursion

In Java, it might look something like this...

    /** Return a list of every sub-list of blocks.
     *  @param  blocks  list of individual block heights
     */
    ArrayList<ArrayList<Integer>>
    generateSubsets(ArrayList<Integer> blocks) {
        return generateSubsets(blocks, blocks.size() - 1);
    }

    /** Return a list of every sub-list of blocks[0], ..., blocks[index].
     *  @param  blocks  list of individual block heights
     *  @param  index  index of last block to consider for subsets
     */
    ArrayList<ArrayList<Integer>>
    generateSubsets(ArrayList<Integer> blocks, int index) {
        ArrayList<ArrayList<Integer>> subsets;
        if (index == -1) {
            subsets = new ArrayList<ArrayList<Integer>>();
            subsets.add(new ArrayList<Integer>());
        } else {
            // Generate the list of subsets for every block except the last.
            subsets = generateSubsets(blocks, index - 1);
            // Make a copy of every subset in the first half, but with the last
            // block added to it.
            int halfSize = subsets.size();
            for (int i = 0; i < halfSize; ++i) {
                subsets.add((ArrayList<Integer>) subsets.get(i).clone());
                subsets.get(subsets.size()-1).add(blocks.get(index));
            }
        }
        return subsets;
    }

Further examples

• "Floor Plan" problem from the DWITE programming contest.

To learn more...

• Wikipedia entry on Brute-force search.

Back to Algorithms

© Copyright 2012–2015 François Pitt <francois.pitt@utoronto.ca>
last updated at 08:24 (EST) on Thu 5 Mar 2015
Algorithms and Data Structures by François Pitt is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.