The Drawing Challenge - a problem I made up and can't solve! I made up the following problem but have not made any headway in solving it in anything less than exponential time. Hopefully somebody can shed some light on it. I'm starting to think it may be $\sf{NP}$-Complete. 

I created a programming challenge type description to encourage my CS friends to have a go at it.



Charlie likes to draw.

He’s given a piece of paper of width $W$ and height $H$ and a list of $N$ numbers $a_1, a_2, a_3, ... a_N$

For each number, he wants to draw a rectangle on the piece of paper. If the rectangle has width $w$ and height $h$ then  $w &gt; 0, h &gt; 0, w \geq h$ and $w \leq W$ and $h \leq H$. Both w and h must be positive integers.

If a number $a_x &gt; a_y$, then $a_x$’s rectangle must have area bigger or equal to $a_y$’s rectangle, where area is $w*h$. If $a_x = a_y$, then they can have different areas.

Charlie doesn’t like to waste ink. For a rectangle of width $w$ and height $h$, he must draw a line of length $2w + 2h$, using $2w + 2h$ units of ink. Clarification: even if two rectangles are adjacent, the adjacent side must be drawn twice.

What is the least units of ink that Charlie can use, drawing one rectangle for each number on the piece of paper, such that no rectangles overlap and the whole paper is covered by rectangles?

Input File:
Line 1       : The width W and height H of the piece of paper, separated by spaces
Line 2       : N, the number of numbers to draw
Lines 3..N+2 : One number on each line.

Constraints: 
W and H are positive integers &lt;= 1000
N is a positive integer &lt;= W * H 
ax, where 1  &lt;= x &lt;= N, is a positive integer &lt;= 1000

Output file:
A single line containing the least units of ink Charlie can use.


Bonus:

Output, for each number ax, the position and size of its rectangle on the piece of paper for a solution that uses the least amount of ink (there can be more than one).

Sample input file:

2 2
4
1
1
1
1


Sample output file:

16


Sample bonus:

-----
| | |
-----
| | |
-----




As pointed out by Marzio, here's the decision problem version:

Given a $W × H$ paper, the numbers $a_1..a_N$ and an amount $K$ of ink, can the $N$ rectangles be drawn, filling the entire paper, as described above?
A closely related problem is strongly NP-hard.

Leung et al. [1] prove that the following decision version of your problem is strongly NP-complete, by reduction from 3-Partition.


  Is it possible to pack $n$ squares of given widths $w_1, w_2, \dots, w_n$ into a larger square of width $W$?


I misread the original question as a generalization of the following decision problem:


  Is it possible to pack $n$ rectangles with given areas $a_1, a_2, \dots, a_n$ into a $H\times W$ rectangle?


The first problem can be reduced to the second as follows: Squares with widths $w_1,\dots,w_n$ can be packed into an outer square of width $W$ if and only if the minimum-perimeter packing of rectangles with areas $w_1^2, \dots, w_n^2$ into a $W\times W$ rectangle uses precisely $4\sum_i w_i$ units of ink.  (Proof: The minimum-perimeter rectangle with any given area is a square.)

However, this reduction does not imply that the actual posted question is NP-hard.


Joseph Y-T. Leung, Tommy W. Tam, C. S. Wong, Gilbert H. Young, and Francis Y. L. Chin.  Packing squares into a square.  J. Parallel and Distributed Computing 10(3):271–275, 1990.