 |
 |
 |
 |
 |
 |
||
 |
 |
 |
 |
 |
| 9 | 1/1 | 返回列表 |
| 查看: 1345 | 回復(fù): 8 | |||
lizh714285金蟲 (小有名氣)
|
[交流]
【趣題鑒賞】最少需要幾個(gè)袋子？ 已有3人參與
|
|
轉(zhuǎn)自“博士數(shù)學(xué)論壇”的一個(gè)帖子 (轉(zhuǎn)載理由：4樓建的01規(guī)劃模型很巧妙，尤其是目標(biāo)函數(shù)的設(shè)置方法，值得推薦) 1# 最少需要幾個(gè)袋子？ 有一堆糖塊N克，總共m塊，分別重a1,a2,a3,.....am克， 現(xiàn)有最多能裝M克的袋子足夠多個(gè)，M>= max{a1,a2,a3,a4....am} 請(qǐng)問最少需要幾個(gè)袋子才能把所有的糖裝完？ 最好能給出方法！補(bǔ)充：所給的袋子都是一樣的。 ------------------------------------------------------------------------------------ 2# 定義：某幾個(gè)糖塊組成的一個(gè)集合A，如果這幾個(gè)糖塊的質(zhì)量之和小于M，則稱A為一個(gè)候選。找出包含a1的所有候選，找出包含a2的所有候選，…，找出包含am的所有候選。取這些候選中質(zhì)量最大的裝入一個(gè)袋子中。繼續(xù)以上的步驟，在有限步內(nèi)即可把所有的糖塊都裝完。 ------------------------------------------------------------------------------------ 3# 首先把所有糖塊按照重量由大到小排列，不妨設(shè)為a01,a02,a03,……,a0m，然后 （1）將目前最重放入袋B1中， （2）看剩下糖塊中最重的能否能放入B1中，如果能重復(fù)（2），如果不能則判斷能不能放入下一個(gè)袋子中，如果能重復(fù)（2）,否則取新袋子裝，后重復(fù)（2），直至所有糖塊都裝入袋子中。 ------------------------------------------------------------------------------------ 4# 這可以使用線性規(guī)劃模型(01規(guī)劃)來求解。 1）將各糖塊編號(hào)命名為1號(hào)糖塊、2號(hào)糖塊、.....m號(hào)糖塊； 2）取m個(gè)袋子，命名為1號(hào)袋子、2號(hào)袋子....m號(hào)袋子； 3）設(shè)決策變量X(i,j); 當(dāng)i號(hào)糖塊在j號(hào)袋子中時(shí)，該變量為1；否則為0 4）約束方程：Σ X(i,j)=1； （說明，和號(hào)下為j=1,和號(hào)上為m）; （意義：每個(gè)糖塊在且僅在一個(gè)袋子中）； 如此對(duì)每個(gè)糖塊建立一個(gè)約束方程，共m個(gè)約束方程。 再對(duì)每個(gè)袋子可裝M克建立m個(gè)約束方程Σ X(ij)*a(i)<=M （說明，和號(hào)下為i=1,和號(hào)上為m）; 如此對(duì)每個(gè)袋子建立一個(gè)約束方程，共m個(gè)約束方程。 5）目標(biāo)函數(shù)，要使袋子盡可能少； 取函數(shù)f(j)=Σ X(i,j) （說明，和號(hào)下為i=1,和號(hào)上為m）， 該函數(shù)表述了j號(hào)袋子中的糖塊數(shù)量. 由于每個(gè)袋子中的糖塊可能是0，1，2，....m個(gè)； 所以f(j) 取系數(shù)1， m+1, (m+1)^2, (m+1)^3， ......, (m+1)^（m-1） ; （共m個(gè)系數(shù)）；命名為c(1),c(2),。。。c(m) 目標(biāo)函數(shù)為 Σ c(j) * f(j) 顯然這是一個(gè)關(guān)于決策變量X(i,j)的線性函數(shù) ； 目標(biāo)函數(shù)最小化；（由于更靠后的袋子中的每個(gè)糖塊，其權(quán)重是相鄰前一個(gè)袋子權(quán)重的m+1倍，按m+1進(jìn)制計(jì)數(shù)自然數(shù)，用幾個(gè)袋子則對(duì)應(yīng)幾位整數(shù) （例如，用4個(gè)袋子，對(duì)應(yīng)目標(biāo)函數(shù)為m+1進(jìn)制的4位數(shù)）；不難證明這個(gè)目標(biāo)函數(shù)確有引導(dǎo)袋子最小化的作用）。 6）初始可行解， X(i,i)=1 , X(i,j)=0(對(duì)i不等于j) 7) 運(yùn)算結(jié)果，獲得了一個(gè)裝糖塊的最優(yōu)方案，不但回答了樓主的問題，而且給出了裝糖果的具體方案 _________________________________________ |
回復(fù)此樓» 猜你喜歡
085600 286分 材料求調(diào)劑
已經(jīng)有4人回復(fù)
-
求調(diào)劑
已經(jīng)有7人回復(fù)
-
275求調(diào)劑
已經(jīng)有10人回復(fù)
-
286求調(diào)劑
已經(jīng)有6人回復(fù)
-
083000學(xué)碩274求調(diào)劑
已經(jīng)有5人回復(fù)
-
【求調(diào)劑】085601材料工程專碩 | 總分272 |
已經(jīng)有5人回復(fù)
-
275求調(diào)劑
已經(jīng)有13人回復(fù)
-
0856，材料與化工321分求調(diào)劑
已經(jīng)有8人回復(fù)
-
085701環(huán)境工程，267求調(diào)劑
已經(jīng)有12人回復(fù)
-
320分，材料與化工專業(yè)，求調(diào)劑
已經(jīng)有7人回復(fù)
» 本主題相關(guān)價(jià)值貼推薦，對(duì)您同樣有幫助:
- 一個(gè)副高帶幾個(gè)學(xué)生的團(tuán)隊(duì)申面上是不是薄弱了？
已經(jīng)有21人回復(fù)
- 小弟的本碩學(xué)歷學(xué)位證書都丟了（放在一個(gè)袋子里丟得），有木有辦法補(bǔ)呢
已經(jīng)有9人回復(fù)
- 女生，華南理工博士復(fù)試，需要穿正裝嗎？
已經(jīng)有24人回復(fù)
- 【求助/交流】細(xì)菌同源重組的同源臂最少需要多少bp呢？
已經(jīng)有7人回復(fù)
- 【求助】下半年加拿大訪問學(xué)者，想申請(qǐng)csc，需要自己辦簽證嗎
已經(jīng)有8人回復(fù)
- 【活動(dòng)】你每天用幾只塑料袋？不論大小
已經(jīng)有42人回復(fù)
- 【求助】求助透析袋子的使用問題。
已經(jīng)有3人回復(fù)
zengpeiwei
金蟲 (著名寫手)
- 應(yīng)助: 0 (幼兒園)
- 金幣: 93.4
- 紅花: 1
- 帖子: 1033
- 在線: 355小時(shí)
- 蟲號(hào): 853973
- 注冊(cè): 2009-09-22
- 性別: GG
- 專業(yè): 有機(jī)合成
★
小木蟲(金幣+0.5):恭喜搶沙發(fā)，給個(gè)紅包
小木蟲(金幣+0.5):恭喜搶沙發(fā)，給個(gè)紅包
| 暈?zāi)?img src="https://muchongimg.xmcimg.com/data/emuch_bbs_images/smilies/shocked.gif" align="absmiddle" border="0"> |
2樓2010-04-14 19:40:46
3樓2010-04-16 13:05:21
小雨萌萌 
銅蟲 (文壇精英)
- 數(shù)學(xué)EPI: 1
- 應(yīng)助: 9 (幼兒園)
- 貴賓: 0.309
- 金幣: 50.4
- 散金: 4018
- 紅花: 20
- 沙發(fā): 1
- 帖子: 11675
- 在線: 261.4小時(shí)
- 蟲號(hào): 952712
- 注冊(cè): 2010-02-05
- 性別: MM
- 專業(yè): 運(yùn)籌學(xué)
4樓2010-04-16 15:33:51
lizh714285
金蟲 (小有名氣)
- 數(shù)學(xué)EPI: 2
- 應(yīng)助: 0 (幼兒園)
- 金幣: 890.9
- 帖子: 94
- 在線: 23.9小時(shí)
- 蟲號(hào): 929249
- 注冊(cè): 2009-12-16
- 專業(yè): 應(yīng)用數(shù)學(xué)方法
★ ★
javeey(金幣+2):謝謝提供解釋 2010-04-16 19:35
javeey(金幣+2):謝謝提供解釋 2010-04-16 19:35
|
我來解釋 線性規(guī)劃，是運(yùn)籌學(xué)中的較為成熟，應(yīng)用較多的一個(gè)模型。 對(duì)一組非負(fù)變量Xi ， 在滿足一組關(guān)于Xi 的線性方程（稱為約束方程）的條件下， 求使得“關(guān)于Xi 的線性函數(shù) c(x)” 取得極大值或極小值的 特解問題。 稱為線性規(guī)劃問題。 （線性條件極值問題） 線性規(guī)劃模型的解法，在運(yùn)籌中研究得較成功。 （解法不成問題），而實(shí)際問題，怎樣化為一個(gè)線性規(guī)劃問題，就是所謂建立線性規(guī)劃模型，并利用線性規(guī)劃模型的算法去解決實(shí)際問題，這才是應(yīng)用者所關(guān)心的問題。 （解法的研究，是另一個(gè)領(lǐng)域，也還有很多研究者在不斷探索） 本例敘述將裝糖塊問題化為線性規(guī)劃問題的建模過程。 第3點(diǎn)，講了變量的選取，一共選了m*m個(gè)變量， X(1,1), X(1,2),...... x(m,m);每個(gè)變量的意義是： x(i,j) 代表第i號(hào)糖塊 將裝進(jìn)第j號(hào)袋子，這件事為真或?yàn)榧佟?br /> 第4點(diǎn)，講約束方程的選擇，一組約束方程是，每個(gè)糖塊在且只在一個(gè)袋子中，例如1號(hào)糖塊，X(1,1)、X(1,2)、X(1,3)、...., X(1,m)中必有一個(gè)為1且其他都為0， 所以它們加起來應(yīng)該為1， 第i號(hào) 糖塊也是如此。所以有m個(gè)方程。 第二組約束方程是，每個(gè)袋子頂多裝M克， 以1號(hào)袋子為例，假設(shè)最優(yōu)解中1號(hào)袋子裝了3號(hào)，7號(hào)，18號(hào)三個(gè)糖塊，x(3,1),X(7,1),X(18,1)會(huì)等于1， X(1,1),X(2,1),X(4,1),X(5,1)....會(huì)等于0； 那么，一號(hào)袋子總重就是X(i,1)=1的那些糖塊重量和，即 Σ X(ij)*a(i)<=M 第5點(diǎn)較為精彩。題目要求是，使袋子盡可能少。 “造一個(gè)關(guān)于X（i,j）的線性函數(shù)，體現(xiàn)使袋子盡可能少�！� 事實(shí)是，因?yàn)樘菈K總數(shù)是m, 所以每個(gè)袋子中最多裝m塊糖，不會(huì)比m多。 我們構(gòu)造了每個(gè)袋子中糖塊數(shù)這一中間過程函數(shù)，f(j)=Σ X(i,j) （對(duì)于每個(gè)袋子求和） f(j) 的值域是0到m的整數(shù)。 用這些袋子糖塊數(shù)共同構(gòu)造m+1進(jìn)制數(shù)字的想法，可以發(fā)現(xiàn)，用袋子最少將對(duì)應(yīng)m+1進(jìn)制數(shù)的最小。 |
5樓2010-04-16 19:17:38
zhixian-ma
木蟲 (正式寫手)
- 應(yīng)助: 54 (初中生)
- 金幣: 2568.7
- 散金: 51
- 紅花: 11
- 帖子: 894
- 在線: 123.2小時(shí)
- 蟲號(hào): 965838
- 注冊(cè): 2010-03-09
- 性別: GG
- 專業(yè): 傳熱傳質(zhì)學(xué)
6樓2010-04-17 12:25:58
★
小木蟲(金幣+0.5):給個(gè)紅包，謝謝回帖交流
小木蟲(金幣+0.5):給個(gè)紅包，謝謝回帖交流
 |
7樓2010-09-12 00:38:50
 |
8樓2010-10-30 13:00:44
9樓2011-04-24 12:13:44
相關(guān)版塊跳轉(zhuǎn)
我要訂閱樓主 lizh714285 的主題更新
| 9 | 1/1 | 返回列表 |
| 最具人氣熱帖推薦 [查看全部] | 作者 | 回/看 | 最后發(fā)表 | |
|---|---|---|---|---|
|
[考研] 286求調(diào)劑 +3 | 丟掉懶惰 2026-03-27 | 6/300 |
|
|---|---|---|---|---|
|
|
[考研] 317求調(diào)劑 +5 | 十閑wx 2026-03-24 | 5/250 |
|
|
[考研] 一志愿華東理工大學(xué)081700，初試分?jǐn)?shù)271 +6 | kotoko_ik 2026-03-23 | 7/350 |
|
|
|
[考研] 085600材料與化工306 +10 | z1z2z3879 2026-03-21 | 11/550 |
|
|
|
[考研] 314求調(diào)劑 +3 | 溪云珂 2026-03-26 | 3/150 |
|
|
|
[考研] 考研調(diào)劑 +9 | 小蠟新筆 2026-03-26 | 9/450 |
|
|
|
[考研] 0703化學(xué)338求調(diào)劑！ +6 | Zuhui0306 2026-03-26 | 7/350 |
|
|
|
[考研] 359求調(diào)劑 +4 | 王了個(gè)楠 2026-03-25 | 4/200 |
|
|
|
[考研] 一志愿鄭州大學(xué)，080500學(xué)碩，總分317分求調(diào)劑 +4 | 舉個(gè)栗子oi 2026-03-24 | 5/250 |
|
|
|
[考研] 總分322求生物學(xué)/生化與分子/生物信息學(xué)相關(guān)調(diào)劑 +5 | 星沉uu 2026-03-26 | 6/300 |
|
|
|
[考研]
 085602化學(xué)工程求調(diào)劑。
+4
|
平樂樂樂 2026-03-26 | 4/200 |
|
|
|
[考研] 機(jī)械學(xué)碩310分，數(shù)一英一，一志愿211本科雙非找調(diào)劑信息 +3 | @357 2026-03-25 | 3/150 |
|
|
|
[考研] 一志愿河工大 081700 276求調(diào)劑 +4 | 地球繞著太陽轉(zhuǎn) 2026-03-23 | 4/200 |
|
|
|
[考研] 0856求調(diào)劑 +8 | zhn03 2026-03-25 | 9/450 |
|
|
|
[考研] 【2026考研調(diào)劑】制藥工程 284分 求相關(guān)專業(yè)調(diào)劑名額 +4 | 袁奐奐 2026-03-25 | 8/400 |
|
|
|
[考研] 300分，材料，求調(diào)劑，英一數(shù)二 +5 | 超贊的 2026-03-24 | 5/250 |
|
|
|
[考研] 0703化學(xué)調(diào)劑，求導(dǎo)師收 +7 | 天天好運(yùn)來上岸?/a> 2026-03-24 | 7/350 |
|
|
|
[論文投稿] 急發(fā)核心期刊論文 +3 | 賢達(dá)問津 2026-03-23 | 5/250 |
|
|
|
[考研] 306求調(diào)劑 +5 | 來好運(yùn)來來來 2026-03-22 | 5/250 |
|
|
|
[考研] 求調(diào)劑院校信息 +6 | CX 330 2026-03-21 | 6/300 |
|