Re: [問題] 一個感覺是 dynamic programming 的題目
看板Prob_Solve (計算數學 Problem Solving)作者keeperkai (keeperkai)時間14年前 (2010/04/23 02:33)推噓1(1推 0噓 0→)留言1則, 1人參與討論串8/12 (看更多)
上一篇太長，以下是我根據loco大的說法寫出來的演算法，
希望各位指正:
input w[],c[]//重量矩陣 耐重矩陣
data structures:
int m[]:用來記錄考慮前i box的時候的可能最高高度
box s[]:一個紀錄在考慮前i box的時候高度最高前提下，重量最小的
解中含有的box set
int maxindex:紀錄當前解結構中重量最大的box的index
int weightofset:紀錄當前解結構的重量總和
想法:
先排序依照capacity的Increasing order，從只考慮第一個箱子開始，
最佳解就是第一個箱子，並且依照loco大的想法運作，依序球出s[n],m[n]
當然s,m不用陣列也可以，因為演算法只會用到上一次解結構的內容，
只是這樣寫比較清楚。
m[i]= m[i-1]+1, c[i]>=w[i]+weightofset
m[i-1], otherwise
s[i]= s[i-1]+box[i], c[i]>=w[i]+weightofset
otherwise
s[i-1]+box[i]-box[maxindex],w[i]<w[maxindex]
s[i-1],otherwise
Algo:
Sort(c[],w[])
m[1]=1
s[1]=box[1]
maxindex=1
weightofset=w[1]
for i= 2 to n
if c[i]>=w[i]+weightofset
m[i]=m[i-1]+1
weightofset=weightofset+w[i]
s[i]=s[i-1]+box[i]
if w[i]>w[maxindex] maxindex=i
else
m[i]=m[i-1]
if (w[i]>=w[maxindex])
s[i]=s[i-1]
else
weightofset=weightofset+w[i]-w[maxindex]
s[i]=s[i-1]+box[i]-box[maxindex]
maxindex=getmaxindex(s[i],w[])//這裡偷懶
本人第一次po文，也並非專業人士，希望各位大大可以"溫和"一點指正(鞭)我XD
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 203.222.23.95
※ 編輯: keeperkai 來自: 203.222.23.95 (04/23 02:34)
※ 編輯: keeperkai 來自: 203.222.23.95 (04/23 02:37)
推
04/23 09:24, , 1F
04/23 09:24, 1F
討論串 (同標題文章)
完整討論串 (本文為第 8 之 12 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
