 |
 |
 |
 |
 |
 |
||
 |
 |
 |
 |
 |
| 5 | 1/1 | 返回列表 |
| 查看: 1350 | 回復(fù): 8 | |||
| 當(dāng)前只顯示滿足指定條件的回帖，點擊這里查看本話題的所有回帖 | |||
lizh714285金蟲 (小有名氣)
|
[交流]
【趣題鑒賞】最少需要幾個袋子？ 已有3人參與
|
||
|
轉(zhuǎn)自“博士數(shù)學(xué)論壇”的一個帖子 (轉(zhuǎn)載理由：4樓建的01規(guī)劃模型很巧妙，尤其是目標(biāo)函數(shù)的設(shè)置方法，值得推薦) 1# 最少需要幾個袋子？ 有一堆糖塊N克，總共m塊，分別重a1,a2,a3,.....am克， 現(xiàn)有最多能裝M克的袋子足夠多個，M>= max{a1,a2,a3,a4....am} 請問最少需要幾個袋子才能把所有的糖裝完？ 最好能給出方法！補充：所給的袋子都是一樣的。 ------------------------------------------------------------------------------------ 2# 定義：某幾個糖塊組成的一個集合A，如果這幾個糖塊的質(zhì)量之和小于M，則稱A為一個候選。找出包含a1的所有候選，找出包含a2的所有候選，…，找出包含am的所有候選。取這些候選中質(zhì)量最大的裝入一個袋子中。繼續(xù)以上的步驟，在有限步內(nèi)即可把所有的糖塊都裝完。 ------------------------------------------------------------------------------------ 3# 首先把所有糖塊按照重量由大到小排列，不妨設(shè)為a01,a02,a03,……,a0m，然后 （1）將目前最重放入袋B1中， （2）看剩下糖塊中最重的能否能放入B1中，如果能重復(fù)（2），如果不能則判斷能不能放入下一個袋子中，如果能重復(fù)（2）,否則取新袋子裝，后重復(fù)（2），直至所有糖塊都裝入袋子中。 ------------------------------------------------------------------------------------ 4# 這可以使用線性規(guī)劃模型(01規(guī)劃)來求解。 1）將各糖塊編號命名為1號糖塊、2號糖塊、.....m號糖塊； 2）取m個袋子，命名為1號袋子、2號袋子....m號袋子； 3）設(shè)決策變量X(i,j); 當(dāng)i號糖塊在j號袋子中時，該變量為1；否則為0 4）約束方程：Σ X(i,j)=1； （說明，和號下為j=1,和號上為m）; （意義：每個糖塊在且僅在一個袋子中）； 如此對每個糖塊建立一個約束方程，共m個約束方程。 再對每個袋子可裝M克建立m個約束方程Σ X(ij)*a(i)<=M （說明，和號下為i=1,和號上為m）; 如此對每個袋子建立一個約束方程，共m個約束方程。 5）目標(biāo)函數(shù)，要使袋子盡可能少； 取函數(shù)f(j)=Σ X(i,j) （說明，和號下為i=1,和號上為m）， 該函數(shù)表述了j號袋子中的糖塊數(shù)量. 由于每個袋子中的糖塊可能是0，1，2，....m個； 所以f(j) 取系數(shù)1， m+1, (m+1)^2, (m+1)^3， ......, (m+1)^（m-1） ; （共m個系數(shù)）；命名為c(1),c(2),。。。c(m) 目標(biāo)函數(shù)為 Σ c(j) * f(j) 顯然這是一個關(guān)于決策變量X(i,j)的線性函數(shù) ； 目標(biāo)函數(shù)最小化；（由于更靠后的袋子中的每個糖塊，其權(quán)重是相鄰前一個袋子權(quán)重的m+1倍，按m+1進制計數(shù)自然數(shù)，用幾個袋子則對應(yīng)幾位整數(shù) （例如，用4個袋子，對應(yīng)目標(biāo)函數(shù)為m+1進制的4位數(shù)）；不難證明這個目標(biāo)函數(shù)確有引導(dǎo)袋子最小化的作用）。 6）初始可行解， X(i,i)=1 , X(i,j)=0(對i不等于j) 7) 運算結(jié)果，獲得了一個裝糖塊的最優(yōu)方案，不但回答了樓主的問題，而且給出了裝糖果的具體方案 _________________________________________ |
回復(fù)此樓» 猜你喜歡
食品工程專碩一志愿中海洋309求調(diào)劑
已經(jīng)有8人回復(fù)
-
求調(diào)劑
已經(jīng)有7人回復(fù)
-
311（085601）求調(diào)劑
已經(jīng)有4人回復(fù)
-
305求調(diào)劑
已經(jīng)有4人回復(fù)
-
一志愿北化085600材料專碩275|有文章專利｜求調(diào)劑
已經(jīng)有7人回復(fù)
-
一志愿華理，數(shù)一英一285求A區(qū)調(diào)劑
已經(jīng)有12人回復(fù)
-
289求調(diào)劑
已經(jīng)有11人回復(fù)
-
生物學(xué)學(xué)碩，一志愿湖南大學(xué)，初試成績338
已經(jīng)有6人回復(fù)
-
321求調(diào)劑
已經(jīng)有7人回復(fù)
-
343求調(diào)劑
已經(jīng)有4人回復(fù)
» 本主題相關(guān)價值貼推薦，對您同樣有幫助:
- 一個副高帶幾個學(xué)生的團隊申面上是不是薄弱了？
已經(jīng)有21人回復(fù)
- 小弟的本碩學(xué)歷學(xué)位證書都丟了（放在一個袋子里丟得），有木有辦法補呢
已經(jīng)有9人回復(fù)
- 女生，華南理工博士復(fù)試，需要穿正裝嗎？
已經(jīng)有24人回復(fù)
- 【求助/交流】細(xì)菌同源重組的同源臂最少需要多少bp呢？
已經(jīng)有7人回復(fù)
- 【求助】下半年加拿大訪問學(xué)者，想申請csc，需要自己辦簽證嗎
已經(jīng)有8人回復(fù)
- 【活動】你每天用幾只塑料袋？不論大小
已經(jīng)有42人回復(fù)
- 【求助】求助透析袋子的使用問題。
已經(jīng)有3人回復(fù)
9樓2011-04-24 12:13:44
小雨萌萌 
銅蟲 (文壇精英)
- 數(shù)學(xué)EPI: 1
- 應(yīng)助: 9 (幼兒園)
- 貴賓: 0.309
- 金幣: 50.4
- 散金: 4018
- 紅花: 20
- 沙發(fā): 1
- 帖子: 11675
- 在線: 261.4小時
- 蟲號: 952712
- 注冊: 2010-02-05
- 性別: MM
- 專業(yè): 運籌學(xué)
4樓2010-04-16 15:33:51
lizh714285
金蟲 (小有名氣)
- 數(shù)學(xué)EPI: 2
- 應(yīng)助: 0 (幼兒園)
- 金幣: 890.9
- 帖子: 94
- 在線: 23.9小時
- 蟲號: 929249
- 注冊: 2009-12-16
- 專業(yè): 應(yīng)用數(shù)學(xué)方法
★ ★
javeey(金幣+2):謝謝提供解釋 2010-04-16 19:35
javeey(金幣+2):謝謝提供解釋 2010-04-16 19:35
|
我來解釋 線性規(guī)劃，是運籌學(xué)中的較為成熟，應(yīng)用較多的一個模型。 對一組非負(fù)變量Xi ， 在滿足一組關(guān)于Xi 的線性方程（稱為約束方程）的條件下， 求使得“關(guān)于Xi 的線性函數(shù) c(x)” 取得極大值或極小值的 特解問題。 稱為線性規(guī)劃問題。 （線性條件極值問題） 線性規(guī)劃模型的解法，在運籌中研究得較成功。 （解法不成問題），而實際問題，怎樣化為一個線性規(guī)劃問題，就是所謂建立線性規(guī)劃模型，并利用線性規(guī)劃模型的算法去解決實際問題，這才是應(yīng)用者所關(guān)心的問題。 （解法的研究，是另一個領(lǐng)域，也還有很多研究者在不斷探索） 本例敘述將裝糖塊問題化為線性規(guī)劃問題的建模過程。 第3點，講了變量的選取，一共選了m*m個變量， X(1,1), X(1,2),...... x(m,m);每個變量的意義是： x(i,j) 代表第i號糖塊 將裝進第j號袋子，這件事為真或為假。 第4點，講約束方程的選擇，一組約束方程是，每個糖塊在且只在一個袋子中，例如1號糖塊，X(1,1)、X(1,2)、X(1,3)、...., X(1,m)中必有一個為1且其他都為0， 所以它們加起來應(yīng)該為1， 第i號 糖塊也是如此。所以有m個方程。 第二組約束方程是，每個袋子頂多裝M克， 以1號袋子為例，假設(shè)最優(yōu)解中1號袋子裝了3號，7號，18號三個糖塊，x(3,1),X(7,1),X(18,1)會等于1， X(1,1),X(2,1),X(4,1),X(5,1)....會等于0； 那么，一號袋子總重就是X(i,1)=1的那些糖塊重量和，即 Σ X(ij)*a(i)<=M 第5點較為精彩。題目要求是，使袋子盡可能少。 “造一個關(guān)于X（i,j）的線性函數(shù)，體現(xiàn)使袋子盡可能少�！� 事實是，因為糖塊總數(shù)是m, 所以每個袋子中最多裝m塊糖，不會比m多。 我們構(gòu)造了每個袋子中糖塊數(shù)這一中間過程函數(shù)，f(j)=Σ X(i,j) （對于每個袋子求和） f(j) 的值域是0到m的整數(shù)。 用這些袋子糖塊數(shù)共同構(gòu)造m+1進制數(shù)字的想法，可以發(fā)現(xiàn)，用袋子最少將對應(yīng)m+1進制數(shù)的最小。 |
5樓2010-04-16 19:17:38
zhixian-ma
木蟲 (正式寫手)
- 應(yīng)助: 54 (初中生)
- 金幣: 2568.7
- 散金: 51
- 紅花: 11
- 帖子: 894
- 在線: 123.2小時
- 蟲號: 965838
- 注冊: 2010-03-09
- 性別: GG
- 專業(yè): 傳熱傳質(zhì)學(xué)
6樓2010-04-17 12:25:58
| 最具人氣熱帖推薦 [查看全部] | 作者 | 回/看 | 最后發(fā)表 | |
|---|---|---|---|---|
|
[考研] 283求調(diào)劑 +3 | A child 2026-03-28 | 3/150 |
|
|---|---|---|---|---|
|
[考研] 070305高分子化學(xué)與物理 304分求調(diào)劑 +4 | c297914 2026-03-28 | 4/200 |
|
|
|
[考研] 320分，材料與化工專業(yè)，求調(diào)劑 +9 | 一定上岸aaa 2026-03-27 | 13/650 |
|
|
|
[考研] 266分，求材料冶金能源化工等調(diào)劑 +7 | 哇呼哼呼哼 2026-03-27 | 9/450 |
|
|
|
[考研] 352分 化工與材料 +5 | 海納百川Ly 2026-03-27 | 5/250 |
|
|
|
[考研] 272求調(diào)劑 +7 | 腳滑的守法公民 2026-03-27 | 7/350 |
|
|
|
[考研] 279 分 求調(diào)劑 +4 | 睡個好覺_16 2026-03-24 | 4/200 |
|
|
|
[考研] 調(diào)劑推薦 +5 | 清酒714 2026-03-26 | 6/300 |
|
|
|
[考研] 材料求調(diào)劑 +5 | .m.. 2026-03-25 | 5/250 |
|
|
|
[考研] 349求調(diào)劑 +4 | 李木子啊哈哈 2026-03-25 | 4/200 |
|
|
|
[考研] 321求調(diào)劑 +6 | wasdssaa 2026-03-26 | 6/300 |
|
|
|
[考研] 【雙一流院校新能源、環(huán)境材料，材料加工與模擬招收大量調(diào)劑】 +4 | Higraduate 2026-03-22 | 8/400 |
|
|
|
[考研] 中國科學(xué)院深圳先進技術(shù)研究院-光纖傳感課題組招生-中國科學(xué)院大學(xué)、深圳理工大學(xué)聯(lián)培 +5 | YangTyu1 2026-03-26 | 5/250 |
|
|
|
[考研] 085600 材料與化工 329分求調(diào)劑 +9 | Mr. Z 2026-03-25 | 9/450 |
|
|
|
[考研] 284求調(diào)劑 +15 | Zhao anqi 2026-03-22 | 15/750 |
|
|
|
[考研] B區(qū)考研調(diào)劑 +4 | yqdszhdap－ 2026-03-22 | 5/250 |
|
|
|
[考研] 340求調(diào)劑 +5 | 話梅糖111 2026-03-24 | 5/250 |
|
|
|
[考研] 上海電力大學(xué)材料防護與新材料重點實驗室招收調(diào)劑研究生（材料、化學(xué)、電化學(xué)，環(huán)境） +4 | 我愛學(xué)電池 2026-03-23 | 4/200 |
|
|
|
[考研] 344求調(diào)劑 +3 | desto 2026-03-24 | 3/150 |
|
|
|
[考研] 335求調(diào)劑 +4 | yuyu宇 2026-03-23 | 5/250 |
|