問題是： 今天有大小分別為8、5、2的貨物, 要放到大小為25的貨櫃(可用多個貨櫃)
求貨櫃數最小的裝法,及此時各貨櫃剩餘的空間
Input: 各種貨物的數量
output: 貨櫃數,各貨櫃剩餘空間
以下是我這個禮拜聽到的方法(幾乎都不是我想到的)
今天聽到還有其他方法,希望同學們不吝指教
(抱歉我認得的人太少了...連他名字都說不出來... ><|| )
方法一： 老師說的簡單Greedy
先填8,再填5,然後是2,
填不下了,或是沒有更小的貨物時,填另一個貨櫃
反例： 8*4, 5*2, 2*4
此法解：(8,8,8) (8,5,5,2,2,2) (2)
最佳解：(8,8,5,2,2)*2
方法一的修正版：先填5,再填8,2
理由,5是25的因數,若有可用5填滿的貨櫃,定可先找出
之後,由於8是2的因數,故Greedy確保有最佳解
反例： 8*2, 5*2, 2*12
此法解：(5,5,8,2,2,2) (8, 2*8) (2)
最佳解：(8,5,2*6)*2
方法二： 找填滿25的整數解，共6組：(8,8,5,2,2) (8,5,5,5,2) (8,5,2*6)
(5*5) (5*3,2*5) (5,2*10)
a) 把6組作排列,先後把可以填滿的貨櫃找出,再作Greedy
反例目前沒有,但其後Greedy不保證是最佳解(?)
b) 先用8的數量較多的解試,依此類推
反例： 5*5, 2*50
此法解：(5*5) (2*12)*4 (2,2)
最佳解：(5,2*10)*5
方法三： 班代提出的"BFS"---廣度優先搜尋
把每一種填法都找出來...時間複雜度n*m*l...
理論上絕對會有最佳解(但是耗時間和空間，且會用到還沒上到的東西)
方法四： DP
問題在....有些人連Greedy都弄不懂...
而且在考慮各貨櫃獨立後,不能只看目前是否有最佳解
(可能現在的填滿了,卻導致找不到最佳解)
注：方法二的Greedy可用DP取代,唯意義不大...
---
以上, 方法三和四應該可以確保有最佳解,但方法四超過進度過多
原先以為二的b是較可行的辦法,但找到反例後,a變成可能是最簡單找到最佳解的方法
剩下的問題是...真的要想那麼多嗎...?
因為...說不定目的是跟老師答案一樣,不是找最佳解...
--
不太重要的p.s.: 作業三難度大幅下降....
Time(作業一) + Time(作業三) << Time(作業二)
--
也許我們人類真的都是破壞的火焰
以自己期望人家的樣子
以自己以為人家的樣子
去改變別人
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.30.100