TopCoder problem "PlacingPieces" used in SRM 316 (Division I Level Two)



Problem Statement

    You have received a new puzzle as a gift. It consists of a board and several pieces of various lengths. Each piece has the same width as the board. The goal of the game is to place the least number of pieces on the board such that no other unused piece can be added legally. Pieces must not hang over the edge of the board or be twisted at an angle. Each piece must be oriented so that its width is parallel to the width of the board. Pieces must not overlap, but their edges may touch. Keep in mind that distances between pieces or the distances between pieces and the edges of the board are not necessarily integer numbers. See the examples for further clarification.



You will be given an int L, the length of the board, and a int[] pieces containing the lengths of the pieces. Create a method optimalPlacement that returns the number of pieces placed on the board that allows you to solve the puzzle.

 

Definition

    
Class:PlacingPieces
Method:optimalPlacement
Parameters:int, int[]
Returns:int
Method signature:int optimalPlacement(int L, int[] pieces)
(be sure your method is public)
    
 

Constraints

-L will be between 1 and 1000, inclusive.
-pieces will contain between 1 and 30 elements, inclusive.
-Each element of pieces will be between 1 and 100, inclusive.
 

Examples

0)
    
9
{1, 8}
Returns: 1

You can place both pieces on the board and leave no space on it. However, there is a better solution as depicted below. Place only the second piece on the board, and leave a little space between it and the left and right edges of the board, so that the first piece can't fit:

1)
    
36
{1, 1, 5, 5, 5}
Returns: 4

If we place all three pieces with length 5 on the board, we will have no choice but to also place the smallest two pieces. However, if you place only two of them and the two smallest pieces, you can leave spaces on the board that are smaller than the length of the remaining piece.

2)
    
37
{1, 1, 5, 5, 5}
Returns: 5
You cannot leave any piece out here.
3)
    
18
{2, 2, 2, 9, 9, 10}
Returns: 2
Sometimes it is better to not place the piece with the highest length.
4)
    
1
{2, 3, 4}
Returns: 0
No piece fits on this board.
5)
    
703
{73, 76, 90, 42, 84, 13, 57, 88, 80, 45, 80, 1, 78, 41, 73, 40, 97, 42}
Returns: 7

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=6540

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=9996&pm=6540

Writer:

_efer_

Testers:

PabloGilberto , brett1479 , vorthys , Olexiy

Problem categories:

Dynamic Programming, Search