PKU1017-Packets

題目：http://poj.org/problem?id=1017
有a1,a2,...,a6個大小是1*1,2*2,...,6*6的方塊
現在要用數個6*6的方框把它們全部裝起來
問最少要幾個方框


程式碼：http://codepad.org/IeHdiRJM
乍聽之下想說「好耶！這真是一道線性規劃問題。」
首先先把裝6*6和5*5的情形砍掉(都是唯一的)
再來枚舉所有可能的方案，隨便列舉四個長這樣：
A.36 0 0 0
B.12 6 0 0
C.5 1 3 0
D.0 5 0 1
.
.
.
好比說A種類放法可以裝36個1*1，C則是5個1、1個2、3個3…等等
對題目要求的a1,a2,a3,a4可以列出以下幾道不等式
a1<=36*A+12*B+5*C+...
a2<=6*B+1*C+5*D+...
a3<=3*C+...
a4<=1*D+...
並且讓成本A+B+C+D+...最小

好耶!!!我們去學單純形法吧!!!

.
.
.
.
.
後來發現6*6方框其實是有玄機的
因為框框實在不大，把6*6、5*5放完以後檢討發現
每個4*4都一定要佔一框，剩下的空間盡量放2*2會是最好的
再檢討放3*3的情形...

發現這道問題有貪心選擇性質，每次盡量放最大的就好了...囧
(請放心，我的程式碼是貪心法而不是線性規劃....)