You have an $8\times 8$ Battleships board and need to place battleships of sizes $1\times 1$, $1\times 2$, $1\times 3$, $1\times 4$, $1\times 5$ on the board to cover as much of the board as possible. The ships cannot touch another ship, even at the corners.
You can place as many of any size as you wish, what is the maximum number of squares you can fill? I believe the answer to this is 30, although not sure how you prove it is the highest.
Also how would you go about solving this for an $n\times n$ board. This probably relates to how you prove the answer for the first part.