 |
 |
 |
 |
 |
 |
||
 |
 |
 |
 |
 |
| 5 | 1/1 | 返回列表 |
| 查看: 1347 | 回復(fù): 8 | |||
| 當(dāng)前只顯示滿足指定條件的回帖，點(diǎn)擊這里查看本話題的所有回帖 | |||
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ī)劃)來(lái)求解。 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； （說(shuō)明，和號(hào)下為j=1,和號(hào)上為m）; （意義：每個(gè)糖塊在且僅在一個(gè)袋子中）； 如此對(duì)每個(gè)糖塊建立一個(gè)約束方程，共m個(gè)約束方程。 再對(duì)每個(gè)袋子可裝M克建立m個(gè)約束方程Σ X(ij)*a(i)<=M （說(shuō)明，和號(hào)下為i=1,和號(hào)上為m）; 如此對(duì)每個(gè)袋子建立一個(gè)約束方程，共m個(gè)約束方程。 5）目標(biāo)函數(shù)，要使袋子盡可能少； 取函數(shù)f(j)=Σ X(i,j) （說(shuō)明，和號(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ù)此樓» 猜你喜歡
086502化學(xué)工程342求調(diào)劑
已經(jīng)有4人回復(fù)
-
材料求調(diào)劑一志愿哈工大324
已經(jīng)有7人回復(fù)
-
328求調(diào)劑
已經(jīng)有7人回復(fù)
-
340求調(diào)劑
已經(jīng)有5人回復(fù)
-
一志愿南昌大學(xué)324求調(diào)劑
已經(jīng)有4人回復(fù)
-
求調(diào)劑推薦 材料 304
已經(jīng)有15人回復(fù)
-
291求調(diào)劑
已經(jīng)有19人回復(fù)
-
331環(huán)境科學(xué)與工程求調(diào)劑
已經(jīng)有3人回復(fù)
-
289求調(diào)劑
已經(jīng)有8人回復(fù)
-
315分求調(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ù)
小雨萌萌 
銅蟲 (文壇精英)
- 數(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
|
我來(lái)解釋 線性規(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ī)劃問題的建模過(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， 所以它們加起來(lái)應(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ù)這一中間過(guò)程函數(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
9樓2011-04-24 12:13:44
| 最具人氣熱帖推薦 [查看全部] | 作者 | 回/看 | 最后發(fā)表 | |
|---|---|---|---|---|
|
[考研] 352分 化工與材料 +5 | 海納百川Ly 2026-03-27 | 5/250 |
|
|---|---|---|---|---|
|
|
[考研] 0856材料化工調(diào)劑 總分330 +10 | zhubinhao 2026-03-27 | 10/500 |
|
|
[考研] 275求調(diào)劑 +10 | Micky11223 2026-03-25 | 13/650 |
|
|
|
[考研] 322求調(diào)劑 +4 | 舊吢 2026-03-24 | 4/200 |
|
|
|
[考研] 材料與化工（0856）304求B區(qū)調(diào)劑 +7 | 邱gl 2026-03-27 | 7/350 |
|
|
|
[考研] 085600，材料與化工321分，求調(diào)劑 +9 | 大饞小子 2026-03-27 | 9/450 |
|
|
|
[考研] 考研調(diào)劑 +10 | 呼呼？~+123456 2026-03-24 | 10/500 |
|
|
|
[考研] 081200-11408-276學(xué)碩求調(diào)劑 +4 | 崔wj 2026-03-26 | 4/200 |
|
|
|
[考研] 351求調(diào)劑 +4 | 麥克阿磊 2026-03-24 | 4/200 |
|
|
|
[考研] 289求調(diào)劑 +17 | 碩星赴 2026-03-23 | 17/850 |
|
|
|
[考研] 297求調(diào)劑 +6 | 田洪有 2026-03-26 | 6/300 |
|
|
|
[考研] 0856求調(diào)劑 +8 | zhn03 2026-03-25 | 9/450 |
|
|
|
[考研] 總分293求調(diào)劑 +6 | 加一一九 2026-03-25 | 8/400 |
|
|
|
[考研] 一志愿南航 335分 | 0856材料化工 | GPA 4.07 | 有科研經(jīng)歷 +6 | cccchenso 2026-03-23 | 6/300 |
|
|
|
[考研] B區(qū)考研調(diào)劑 +4 | yqdszhdap－ 2026-03-22 | 5/250 |
|
|
|
[考研] 340求調(diào)劑 +5 | 話梅糖111 2026-03-24 | 5/250 |
|
|
|
[考研] 上海電力大學(xué)材料防護(hù)與新材料重點(diǎn)實(shí)驗(yàn)室招收調(diào)劑研究生（材料、化學(xué)、電化學(xué)，環(huán)境） +4 | 我愛學(xué)電池 2026-03-23 | 4/200 |
|
|
|
[考研] 求調(diào)劑 +6 | 研研，接電話 2026-03-24 | 7/350 |
|
|
|
[考研]
 材料考研調(diào)劑生
+3
|
黃粱一夢(mèng)千年 2026-03-24 | 3/150 |
|
|
|
[考研] 070300，一志愿北航320求調(diào)劑 +3 | Jerry0216 2026-03-22 | 5/250 |
|