演算法問題 : 如果把積木分配在箱子內

Question

請先看這裡 :
下面是我要做的程式的其中一小部分, 其實還有更多要求
其中重點是如何在下面兩大問題取得平衡點(即同時符合兩者的基本要求)
我的程式是用C寫, 但我也懂部分的C++語言, 所以可用上C/C++解說
當然問題是演算法, 文字解釋也沒有問題的, 最後先謝謝各位的幫助
這個問題我會給20點分數的! 希望得到大家的努力來解答我的問題吧
－　　－　　－　　－　　－　　－　　－　　－　　－　　－　　－　　－

如果可以寫一個程式出來, 自動把一埋積木分配入箱子內
積木及箱子都是正方體, 積木以1x1x1cm立方為1單位
箱子以3x3x3cm立方為1單位
用戶會輸入積木每件的體積(n單位, 其中n是正整數)
箱子數目是無限的, 但程式要求以最小的箱子放好各件積木
別想到數學中的三維立體空間問題! 題目還未完的
假設有一件體積是3單位的積木, 程式可以把這件積木斬開成3件1單位來分配
但這3件積木必須分配在同一個箱子內
箱子數目必須是最小的, 而且要把27個單位的空間用盡

例外情況: 當一件積木體積大於27時, 可以把它斬開成2件處理
而分開放在2個箱子內, 大於81的斬開成3件...如類推

例外情況2: 箱子內的積木允許有疊高的情況, 即每個箱子可以超出27單位
但須要盡量減少這個情況出現(不可能太多的箱子也超出)
例如分配的結果有2個,
(1) 是由Y個箱子放N件積木, 其中只有2個箱子都超出了1單位
(2) 是由(Y-1)個箱子放N件積木, 其中有7個箱子都超出了1單位
程式須要選出(1)的結果, 至於詳細的選擇條件可以留給大家決定
而超出的限額由用戶決定, 但不能太大(建議限制小於9)

現在所有積木都有顏色(只有黑和白2種)
程式須要計算黑積木告白積木的體積比例
然後根據這個比例分配積木到箱子中
注意每一個箱子中的黑白積木比例要做到接近先前計算出的比例
並且須要同時符合最前面的要求

如果不太明白我所說的, 可以給我留言問過究竟
e-mail : [e-mail]
icq# : 292277186
web page : http://chicorita.24cc.cc

錯誤更正 :
例外情況 - 當一件積木體積大於27時, 可以把它斬開成2件處理
而分開放在2個箱子內, 大於81的斬開成3件...如類推

這裡大於81的斬開成3件應改為4件

Answer 1

三個問題
1.“程式可以把這件積木斬開成3件1單位來分配. 但這3件積木必須分配在同一個箱子內”. 從這得知同一件積木的小積木要擺在同一個箱子裡. 那如果你有兩件積木. 一個26, 另一個26. 怎麼辦?
2.在例外情況中, 既每箱可裝27單位. 所以對這句”當一件積木體積大於27時, 可以把它斬開成2件處理而分開放在2個箱子內”了解. 但就不了解這句了” 大於81的斬開成3件”. 因該是4件才對. 大於27裝2件, 大於54裝3件, 大於81應是裝4件才對啊.

2005-05-06 06:50:15 補充：
3.在例外情況2中的最後一句,”建議限制小於9”. 是建議總共限制小於9單位還是每箱9單位. 也就是說用戶決定的是每箱還是總共?

2005-05-14 12:02:52 補充：
Can I post in English?

2005-05-17 07:07:11 補充：
Okay, here is what I think.
All we know is that there are number of lego pieces where each pieces has different size. It does not matter what shape the lego piece has. We need to put it into a number of boxes which has the least amount of violations.

What is a violation? Easiest form of violation is like what you stated in your problem. If one box has more than 27 lego pieces then there will be one violation per lego pieces that are over 27. However, I also added that if one box has less than 27 lego pieces then there will also be one violation per lego pieces that are under 27. Another word, a box can have no violation if and only if there are exactly 27 lego pieces. And of course, if you split one lego then that will be one violation. A more advance form of violation will be a weighted violation. For example, if one box has less than 27 lego pieces then instead of having one violation per lego pieces that are under 27. We can set it to have 0.1 violations per lego pieces that are under 27. In another word, if a box has 17 lego pieces, it will take only 1 violation instead of 10.

So we know that we have two extreme cases.

1. we can start with one box that we stuff all the lego pieces into it.
2. we can let each lego pieces has it's own boxes.

So that's suppose X meaning the number of lego pieces we have and Y meaning how many boxes we need in the second case. So the best way to put them into the boxes will be one of the permutations in the set of permutations generated by X and Y. So You'll need to have two loops to generate all the permutations. Once you generate one permutation, you need to go ahead and record number of violations it has. if it has none then you got the best way to put all the lego pieces into the boxes. If you didn't encounter any permutation produce 0 violations then you need to pick the one permutation that has the least amount of violations to be your best way to put all the lego pieces into the boxes.

for example, you have 3 pieces of lego 5, 7, and 16. The number of boxes needed is 3. because one can be in its own
box. So here are the permutations starting from just one box to 3 boxes:

permutations/violations
5 + 7 + 16----->1
5+7, 16-------->15+11=26
5, 7 + 16------->22+4=26
5+16, 7-------->6+20=26
5, 7, 16-------->22+20+11=53

So from the table. The best permutations will be the first one which only have 1 violations.

of course, this is just one way to solve this problem and can be improved by bring more factor into the picture. However, the basic idea is there.

Understand what I am trying to say here? If you have more questions, let me know.

2005-05-18 21:07:28 補充：
條條大路通羅馬.我講的只不過是我隨手想出的方法.若你有更好的方法那更好啊... :)

Answer 2

●九州 娛樂 網站 http://ts777.cc
●●●運彩遊戲、真人遊戲、電子遊戲、對戰遊戲、對戰遊戲●●●

●新舊會員儲值就送500點

● 真人百家樂彩金等你拿

●線上影片直播、正妹圖、討論區免費註冊

歡迎免費體驗交流試玩!

●九州 娛樂 網站 http://ts777.cc

Answer 3

別把問題丟到我信箱啦~"~
C++我還不會！
明天要考試了@@"

Answer 4

我想這是一個生產線要包裝產品的問題箱子可以裝27件產品,每樣產品都有一定的批量,
例外1要先解決,使所有的產品批量數目都小於27,也就是多於27的數量先包裝成一箱(剩下的都小於27)
再看看是否有多件產品,加總後是27的先取出(滿箱)
剩下的就是排序了,先依序將產品分到各箱中,這可能箱子數量很高,再一一對換,找最小的箱數
例外2最後再解決,先不考慮黑白的問題,因為黑白可能是重量的問題,也就是產品有可能有不同的重量,希望包裝的箱子重量儘可能一致

Answer 5

我對例外情況2有疑問, 這一個條件似乎有ambiguity

也就是說,可以疊高但儘量不要超過,可是題目原本又是求最少箱子數量,這樣似乎有問題,畢竟,如果我讓每個箱子都超過一點 (1以上個單位),或許就可以少用一個箱子?

Answer 6

回龍的問題 :

1. 如果有2件體積26單位的積木, 答案會是由2個箱子各放1件積木
這裡補充一點, 每個箱子不必全滿的, 但用2個箱子以經是最小

2. 這是算術上的問題, 斬開成2件處理是因為所有箱子都不足夠大
所以會打破了"同一件積木放在同一個箱子裡"的條件
而例外情況就可以解決這個問題, 假設一件體積54單位的積木,
須斬成2件27,27的放在2個不同箱子
"大於81應是裝4件才對", 是我的錯誤...在此更改這個錯誤, 謝謝你的提點

2005-05-06 20:38:08 補充：
回龍的問題 :
3. 這個9的限制是由設計者決定的, 所以你喜歡多少也沒有問題
但更進一步的程式設計, 這個限制是由用戶決定... 你可以選擇要怎樣做的

2005-05-06 21:05:06 補充：
回rock的問題:
果然聰明哦! 我的原題目確是英文版
而我現在發問的問題是由我譯成中文的
大概我的描述太簡單或者含糊不清, 有什麼不明白的地方就盡情問吧
(1) 程式要求以最小的數目的箱子來分配好各件積木
(2) 程式的確不在乎積木的形狀, 而是積木的體積,
及一件積木的所有部分須放在同一個箱子內 (除例外情況, 或有更好的解決方案)
[字數超出300, 下面續]

2005-05-06 21:05:25 補充：
[續上面]
再詳情說明一點 : 更好的解決方案是指一個足夠大的積木但體積未超越27單位
程式仍可以使用例外情況處理, 把積木斬件, 但有以下的限制
1> 最關鍵的條件 : 一個體積未超越27單位的積木如果在斬件的情況下得出的解決方案
比不斬件的情況的好(分配剛剛好, 使用的箱子/例外情況2較少等等), 程式應選擇前者
2> 足夠大的積木的定義由設計者決定 (我的建議是當體積超越16單位)
3> 把積木斬件的件數, 當然不可以把積木分成太多件數 (建議每件最小為8單位)

2005-05-08 18:25:00 補充：
回Anthony Liu:
[第1部分, 共2部分]
這個問題是由設計的人決定, 超出就是例外情況
而例外亦應該有個限度的, 如果使用得太多例外的就不用寫個程式出來了
如果有756件單位是1的積木, 很自然就會計算得到用28個箱, 各放27件
但如果使用例外情況, 可以用27個箱, 各放28件, 那麼就少了一個箱, 不是更好嗎?
錯了, 這個方法使用了27次的例外, 雖然各箱子都只超出1, 就能用少1個箱
但有一個不用任何例外而能完美分配的解答, 當然比用上27次例外的解答好
我建議在尋找最好的解答前可先去除所有條件而得出的答案作為參考

2005-05-08 18:26:06 補充：
[第2部分, 共2部分]
例如有8件體積分別為4,5,6,7,8,8,9,12積木, 它們的體積總和是59, 應該須要3個箱子的
很容易想到有以下2種解答 : A- [4,7,8,8] [6,9,12] [5] , B- [4,5,6,7,8] [8,9,12]
當然數字的分配還有很多, 但我們先看這兩個解答...A用3個箱子, B用2個箱子
是不是B的解答好呢? 這個程式沒有一項條件說明愈用少箱就愈好哦!
既然參考答案都得出3個箱子以經使用最少的箱子, 所以A的解答比B的好
就算A的第3個箱是1而不是5, A仍是最佳解答, 因為A的第1,2個箱子都是全滿

2005-05-08 18:26:46 補充：
[回Anthony Liu的補充]
如果現在A是[4,7,8,8] [6,9,10] [3], B是[4,7,8,8] [6,9,10,3]
現在2個解答都可以接受(在這種情況當然是由設計者決定)

2005-05-09 22:02:42 補充：
please help me!! 我快要死了

2005-05-12 16:49:01 補充：
回LinuxUser:
我覺得這個題目不能看成包裝,
因為包裝時一定要指定數目才包起(例如12打, 50件...)
這個題目允許數目超出或小於的...所以不太像了,
但你喜歡的也可以當成包裝程式

其實我也想過你的方法, 就是先把能夠放滿一個箱子積木處理好,
然後才分配餘下的, 但這個方法會不會有漏洞出現呢?
分配的問題往往會出現幾個甚至數十個答案, 如果先把一些積木拿走
到後來餘下的積木會不會須要配合拿走的積木才能組合一個更好的解答?
真的想爆頭了...想到些少又怕會有看不見的錯誤, 令我完全不敢動手寫這個程式

2005-05-14 09:58:48 補充：
回星光工作室:
對不起哦...阻住你考試溫書
但是這個問題跟程式語言無直接關係的! 不會C++也不成問題呢

2005-05-14 23:49:28 補充：
re龍: sure!

Answer 7

怎麼覺得這個問題好像是從英文翻譯成中文的一樣 都看不懂它在表達什麼
"程式要求以最小的箱子放好各件積木"---->到底是要用的箱子最小 還是 最少....
"體積是3單位的積木, 程式可以把這件積木斬開成3件1單位來分配，但這3件積木必須分配在同一個箱子內"...是否為說明程式不在乎積木的形狀?