iT邦幫忙

1

裝箱收納空間的程式

2019/10/01 希望對有同樣問題的人有幫助

https://stackoverflow.com/questions/6686979/cutting-stock-problem

https://zh.wikipedia.org/wiki/%E9%81%8B%E7%B1%8C%E5%AD%B8

2019/09/26 00:44 問題尚未解決 //但動態規劃(背包問題)似乎行得通

詳細述目前的問題:

有三種箱子可以選擇,分別可以裝8、10、12格

有數個物品大小不一,每個物品持有的數量不一。  
       *物品大小必需可以是小數*

將所有物品塞進箱子,每裝一個箱子都要加入成本考量。然後把組合列出來

=============
2019/09/22 00:28
X暴力列舉法
在一剛開始面對這問題時採用暴力列舉法,我實際帶了幾個數字進去,也成功列出有效組合。
當我接著要替組合寫判斷時才覺得不對,如果我有N個數字呢?

我得列2ⁿ種組合,如果 n=3 那還好 ,那 n=20 呢? 那會有超過1000000種組合!!

2019/09/26 00:44
X貪婪演算法
當下列出的組合是最佳的。但就整體而言不一定是最佳的。

=============

看更多先前的討論...收起先前的討論...
ccutmis iT邦高手 10 級 ‧ 2019-09-21 12:51:59 檢舉
這是作業嗎?
cuxiapple iT邦新手 4 級 ‧ 2019-09-21 13:46:58 檢舉
我知道你把程式想太複雜 你把遊戲規則設定太複雜
你先把三個箱子寫出來 之後再考慮如何監控數量問題
小魚 iT邦高手 1 級 ‧ 2019-09-21 14:52:45 檢舉
這只是一維的問題吧,
我還以為是要處理二維的.
newkevin iT邦高手 1 級 ‧ 2019-09-21 15:06:33 檢舉
如果想不出來
1.就手動阿 實物模擬阿
2.用EXCEL也可
PS 先用中文寫出來 然後再找規則 在寫程式
可以先 物品欄格式數少 1 2 3 或 234
先簡化條件 物品1格 在進階 2格等
列出來 如何計算
物品欄 多少空格
剩餘空格
如何比較剩餘空格數 物品的格數
...........
這應該是DP吧?
建議可以去看看Algorithm背包問題那一章
----------
不。我發現我想太多了,他只要求剩餘的話,你可以先將確定會滿格的填滿,然後再去處理剩下來的物品就好了。
ccutmis iT邦高手 10 級 ‧ 2019-09-21 23:31:18 檢舉
寫好了...

Box Volume: 12 Contain: 7,5
Box Volume: 12 Contain: 7,5
Box Volume: 8 Contain: 5,3
Box Volume: 8 Contain: 5,3
Box Volume: 10 Contain: 3,3,3
用完物品 剩餘空間 1
蟹老闆 iT邦大師 1 級 ‧ 2019-09-23 01:20:14 檢舉
如果那個格子有高度則跟貨櫃裝櫃相同原理可以參考這個公式(關鍵字:CBM),要考慮的是零碎位置如何塞好塞滿
長x寬x高(公分)x 0.0000353 = _______ Cuft (即 Cubic Feet 立方呎)
_______ Cuft ÷ 35.315 = ______ CBM (即 Cubic Meter立方米)

看看有無幫助
https://www.uec.com.tw/volume-calculation.html
http://tonysnote.blogspot.com/2010/09/1cbmcbft35315cbm0006.html
chebub iT邦新手 5 級 ‧ 2019-09-23 10:56:25 檢舉
@長風青雲 背包問題---它可以找到當前最佳組合,但不能找到整體最佳組合

@蟹老闆 可以先記著也許以後會用到
1
海綿寶寶
iT邦超人 1 級 ‧ 2019-09-21 15:19:23

我替你邀請了四位帥哥和一位美女來回答你的問題
分別是
tmt514
River
harry_xie
長風青雲
以及
Fion

如果都沒人回答出你的問題

選我正解

小魚 iT邦高手 1 級 ‧ 2019-09-21 16:15:29 檢舉

海綿寶寶認識這些人喔?

1
harry_xie
iT邦新手 5 級 ‧ 2019-09-21 17:56:39

我說說自己觀察到的點:
A佔3格+B佔5格,正好等於有8格空間的物品欄
A佔3格+C佔7格,正好等於有10格空間的物品欄
B佔5格+C佔7格,正好等於有12格空間的物品欄

根據這些資訊,將4個A物品和4個B物品放到8格的物品欄
剩下的1個A物品和1個C物品放到10格的物品欄
留下的最後1個C物品放到8格的物品欄,得出所有箱子的剩餘空間總和為1,這種情況就是最少的了

您這是人工智慧的答案
樓主可能需要的是用程式解題

newkevin iT邦高手 1 級 ‧ 2019-09-21 21:32:52 檢舉

如果確定你觀察的沒錯 其實有錯也沒關係
你的程式怎麼寫
有三個物品欄 如何給他幾格
怎麼確定 定義 甚麼物品占幾格
這兩個先寫出來
阿不同人 呵呵

chebub iT邦新手 5 級 ‧ 2019-09-23 20:47:35 檢舉

其實我也覺得這問題有牽涉到人工智慧 :\

所以我在想另一個方案:先列出所有可能的組合,再讓人工下去挑選

@海綿寶寶
@newkevin

0
小魚
iT邦高手 1 級 ‧ 2019-09-21 18:46:57

我覺得,
請你先把目前覺得最接近解答的程式碼貼出來,
大家再幫你看看.

1
tmt514
iT邦新手 5 級 ‧ 2019-09-21 21:54:46

我覺得你的題目跟 Leetcode 這題很像唷:https://leetcode.com/problems/shopping-offers/
這個題目是這樣的:每個商品有一個單價、然後有一些折價組合(比方說一個A和一個C湊在一起只要 $1),你的目標是要購得恰好 5個A、4個B、2個C。

  • 可以把「剩餘空間」當作「花費」來計算。以你的例子,A的單價是 $5、B的單價是 $3、C的單價是 $1。
  • 你可以把所有湊出 8格、10格、12格的方法蒐集起來,這些只要湊得出來都是「免費」的(因為沒有剩餘空間)
  • 你可以把所有湊出少於 8格、9格、11格的方法蒐集起來,湊出這些所需要的錢就等於找一個最小的箱子裝箱完以後的剩餘格子數。

說不定有更好的作法XDDDDD

chebub iT邦新手 5 級 ‧ 2019-09-23 23:30:41 檢舉

雖然沒看懂 不過可以研究一下這個網站 :D

2
ccutmis
iT邦高手 10 級 ‧ 2019-09-22 12:32:53

嘉義彭于晏 不是 彭于晏
JAVASCRIPT 也不是 JAVA
我沒學過 JAVA ,只能用 JAVASCRIPT 來實作...
/images/emoticon/emoticon82.gif

demo url: http://www.web3d.url.tw/ITHELP/JS_20190922/index.htm

演算法寫好了在下方說明,JS源碼已更新,
寫的很差就不貼上來傷邦友的眼睛了,想了解糟CODE者請自行點上面連結觀看html原始碼。

演算法說明 -- 2019/09/25

說明(1):
BoxObject物件.屬性 
 vol(整數) 用以決定該box的最大容量
 contain(陣列) 用以存放item

BoxObject物件.方法 
 calcArea() 取得剩餘容量 0:已滿
 doPushItem() 把item放入contain

分箱打包邏輯如下:

箱子有三種容量(12,10,8)

我們有三種物品分別佔(7,5,3)格箱子空間,物品數量不固定,

這裡先以箱子容量跟物品佔格數作分析

12格的箱子可放置物品組合為
[7]+[5] 或 [3]+[3]+[3]+[3]

10格的箱子可放置物品組合為
[7]+[3] 或 [5]+[5] 

8格的箱子可放置物品組合為
[5]+[3] 

理出上列的組合就能開始寫程式了,假設我們全部物品為
[7][7][3][3][3][3][3][5][5][5][5]

先將它們由大到小排序
[7][7][5][5][5][5][3][3][3][3][3]

零、取出物品先判斷是否為3或5或7,
若是才繼續後面流程,若不是則將物品放入usefulArr 陣列並跳到下一輪廻圈

一、取出第一個物件為[7],
搜其它全部物品是否有[5],有的話就建立 容量[12]的箱子,
若無則搜其它全部物品是否有[3],有的話就建立 容量[10]的箱子,
若無則建立 容量[8]的箱子,
把[7]放進剛才建立的箱子。

二、取出第二個物件為[7],
搜其它全部物品是否有[5],有的話就建立 容量[12]的箱子,
若無則搜其它全部物品是否有[3],有的話就建立 容量[10]的箱子,
若無則建立 容量[8]的箱子,
把[7]放進剛才建立的箱子。

三、取出第三個物件為[5],
檢查已建立的箱子是否有空間可放入,
有則放入有空間的箱子。
把[5]放進箱子[0]。

四、取出第四個物件為[5],
檢查已建立的箱子是否有空間可放入,
有則放入有空間的箱子。
把[5]放進箱子[1]。

五、取出第五個物件為[5],
檢查已建立的箱子是否有空間可放入,有則放入有空間的箱子,
若無則表示最大的物件7已經全部處理完了,
*再來是最難處理的部份(中跟小零碎物件如何分配最佳利用空間)
若無則搜其它全部物品是否有[3],有的話就建立 容量[8]的箱子,
若無則搜其它全部物品是否有[5],有的話就建立 容量[10]的箱子,
若無則建立 容量[8]的箱子,
把[5]放進箱子[2]。

六、取出第六個物件為[5],
檢查已建立的箱子是否有空間可放入,有則放入有空間的箱子,
若無則表示最大的物件7已經全部處理完了,
若無則搜其它全部物品是否有[3],有的話就建立 容量[8]的箱子,
若無則搜其它全部物品是否有[5],有的話就建立 容量[10]的箱子,
若無則建立 容量[8]的箱子,
把[5]放進箱子[3]。

七、取出第七個物件為[3],
檢查已建立的箱子是否有空間可放入,有則放入有空間的箱子,
把[3]放進箱子[2]。

八、取出第八個物件為[3],
檢查已建立的箱子是否有空間可放入,有則放入有空間的箱子,
把[3]放進箱子[3]。

九、取出第九個物件為[3],
檢查已建立的箱子是否有空間可放入,有則放入有空間的箱子,
若無則表示目前只剩最小的物件,
計算全部物件加總格數N(包含剛才取出的[3])這邊計算結果為9,
依加總數來決定要建立的箱子,N>9就建立 容量[12]的箱子,
若無並且N==9就建立 容量[10]的箱子,
若無並且N<9就建立 容量[8]的箱子,
把[3]放入箱子[4]。

十、重覆步驟九直到全部物件裝箱即完成。

看更多先前的回應...收起先前的回應...
chebub iT邦新手 5 級 ‧ 2019-09-23 10:53:48 檢舉

我會需要一些時間去吸收 :D

ccutmis iT邦高手 10 級 ‧ 2019-09-23 10:54:40 檢舉

/images/emoticon/emoticon12.gif

chebub iT邦新手 5 級 ‧ 2019-09-23 12:52:33 檢舉

可以請C大細述程式邏輯嗎?

ccutmis iT邦高手 10 級 ‧ 2019-09-23 15:00:02 檢舉

 

chebub iT邦新手 5 級 ‧ 2019-09-23 15:49:28 檢舉

因為當我添加不同數字時,程式就壞掉了

ccutmis iT邦高手 10 級 ‧ 2019-09-23 16:02:28 檢舉
chebub iT邦新手 5 級 ‧ 2019-09-25 20:50:27 檢舉

C大 這幾天我找到 動態規劃(經典背包問題)這個概念,跟我遇到的問題似乎有些關聯
目前還沒有深入了解 分享給你

ccutmis iT邦高手 10 級 ‧ 2019-09-25 21:17:02 檢舉

謝謝分享不過我已經想到合理而且能處理這個打包問題的邏輯了,有時間再把它更新上去。上面本文的程式也會重寫過...

chebub iT邦新手 5 級 ‧ 2019-09-25 21:27:13 檢舉

https://luke2336.blogspot.com/2018/06/knapsack-problem.html

你看! 這篇真的是說到心坎裡 期初設計真的就是找最佳組合 發現不對 再暴力列舉所有組合 結果完全沒有考慮到一旦組合數量龐大會很恐怖 XD

ccutmis iT邦高手 10 級 ‧ 2019-09-25 23:04:40 檢舉

裝箱打包邏輯我有在上面本文區更新了,有空參考看看...

我要發表回答

立即登入回答