ある面積に図形をできるだけ多く配置するためには、どのように計算したらいいでしょうか？

「与えられる領域と図形はともに矩形である」という前提をおいてよいのでしょうか。その場合の解法は比較的単純だと思います。以下の手順を踏みます。

1. 与えられた領域に対して、左上から右下にかけて、与えられたサイズの矩形をぴったり隙間が出来ないように配置する
2. 与えられた領域と図形のサイズによっては領域の右側あるいは下側が余るので、その部分に図形を90度回転して配置できないかチェックし、もし配置できるなら配置する
3. 1.において最初に90度回転した状態で配置した方がより多くの図形を配置できる場合もあるので、その場合とどちらが多くの図形を配置できるかチェックし、より多く配置できる方を採用する
4. 3.で採用した最終的な図形の配置を出力する

（配置できる図形の数が等しい複数のパターンが存在する場合は、それぞれのパターンを出力するようにしました）

上記の手続きを実現するC言語のソースコードは以下のようになります（長いのでリンク先に示しました）。

http://gist.github.com/130568

実際にコーディングする際は、ループの境界条件や図形の縦横のサイズが同じ場合などに注意する必要があります。

なお、問題文が「矩形以外、たとえば円や矩形以外の多角形も受け付ける」ということでしたら、当然アルゴリズムはずっと複雑になり、ちょっと今は解法を思いつかないので、その場合は他の回答者の方に譲ります。