 |
 |
 |
 |
 |
 |
||
 |
 |
 |
 |
 |
| 9 | 1/1 | 返回列表 |
| 查看: 1348 | 回復: 8 | |||
lizh714285金蟲 (小有名氣)
|
[交流]
【趣題鑒賞】最少需要幾個袋子？ 已有3人參與
|
|
轉自“博士數(shù)學論壇”的一個帖子 (轉載理由：4樓建的01規(guī)劃模型很巧妙，尤其是目標函數(shù)的設置方法，值得推薦) 1# 最少需要幾個袋子？ 有一堆糖塊N克，總共m塊，分別重a1,a2,a3,.....am克， 現(xiàn)有最多能裝M克的袋子足夠多個，M>= max{a1,a2,a3,a4....am} 請問最少需要幾個袋子才能把所有的糖裝完？ 最好能給出方法！補充：所給的袋子都是一樣的。 ------------------------------------------------------------------------------------ 2# 定義：某幾個糖塊組成的一個集合A，如果這幾個糖塊的質量之和小于M，則稱A為一個候選。找出包含a1的所有候選，找出包含a2的所有候選，…，找出包含am的所有候選。取這些候選中質量最大的裝入一個袋子中。繼續(xù)以上的步驟，在有限步內(nèi)即可把所有的糖塊都裝完。 ------------------------------------------------------------------------------------ 3# 首先把所有糖塊按照重量由大到小排列，不妨設為a01,a02,a03,……,a0m，然后 （1）將目前最重放入袋B1中， （2）看剩下糖塊中最重的能否能放入B1中，如果能重復（2），如果不能則判斷能不能放入下一個袋子中，如果能重復（2）,否則取新袋子裝，后重復（2），直至所有糖塊都裝入袋子中。 ------------------------------------------------------------------------------------ 4# 這可以使用線性規(guī)劃模型(01規(guī)劃)來求解。 1）將各糖塊編號命名為1號糖塊、2號糖塊、.....m號糖塊； 2）取m個袋子，命名為1號袋子、2號袋子....m號袋子； 3）設決策變量X(i,j); 當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）目標函數(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) 目標函數(shù)為 Σ c(j) * f(j) 顯然這是一個關于決策變量X(i,j)的線性函數(shù) ； 目標函數(shù)最小化；（由于更靠后的袋子中的每個糖塊，其權重是相鄰前一個袋子權重的m+1倍，按m+1進制計數(shù)自然數(shù)，用幾個袋子則對應幾位整數(shù) （例如，用4個袋子，對應目標函數(shù)為m+1進制的4位數(shù)）；不難證明這個目標函數(shù)確有引導袋子最小化的作用）。 6）初始可行解， X(i,i)=1 , X(i,j)=0(對i不等于j) 7) 運算結果，獲得了一個裝糖塊的最優(yōu)方案，不但回答了樓主的問題，而且給出了裝糖果的具體方案 _________________________________________ |
回復此樓» 猜你喜歡
329求調(diào)劑
已經(jīng)有5人回復
-
材料求調(diào)劑一志愿哈工大324
已經(jīng)有8人回復
-
286求調(diào)劑
已經(jīng)有7人回復
-
083000學碩274求調(diào)劑
已經(jīng)有7人回復
-
311求調(diào)劑
已經(jīng)有8人回復
-
一志愿C9材料與化工專業(yè)總分300求調(diào)劑
已經(jīng)有9人回復
-
311求調(diào)劑
已經(jīng)有3人回復
-
291求調(diào)劑
已經(jīng)有6人回復
-
一志愿廈門大學化學學碩307求調(diào)劑
已經(jīng)有9人回復
-
286求調(diào)劑
已經(jīng)有10人回復
» 本主題相關價值貼推薦，對您同樣有幫助:
- 一個副高帶幾個學生的團隊申面上是不是薄弱了？
已經(jīng)有21人回復
- 小弟的本碩學歷學位證書都丟了（放在一個袋子里丟得），有木有辦法補呢
已經(jīng)有9人回復
- 女生，華南理工博士復試，需要穿正裝嗎？
已經(jīng)有24人回復
- 【求助/交流】細菌同源重組的同源臂最少需要多少bp呢？
已經(jīng)有7人回復
- 【求助】下半年加拿大訪問學者，想申請csc，需要自己辦簽證嗎
已經(jīng)有8人回復
- 【活動】你每天用幾只塑料袋？不論大小
已經(jīng)有42人回復
- 【求助】求助透析袋子的使用問題。
已經(jīng)有3人回復
zengpeiwei
金蟲 (著名寫手)
- 應助: 0 (幼兒園)
- 金幣: 93.4
- 紅花: 1
- 帖子: 1033
- 在線: 355小時
- 蟲號: 853973
- 注冊: 2009-09-22
- 性別: GG
- 專業(yè): 有機合成
2樓2010-04-14 19:40:46
3樓2010-04-16 13:05:21
小雨萌萌 
銅蟲 (文壇精英)
- 數(shù)學EPI: 1
- 應助: 9 (幼兒園)
- 貴賓: 0.309
- 金幣: 50.4
- 散金: 4018
- 紅花: 20
- 沙發(fā): 1
- 帖子: 11675
- 在線: 261.4小時
- 蟲號: 952712
- 注冊: 2010-02-05
- 性別: MM
- 專業(yè): 運籌學
4樓2010-04-16 15:33:51
lizh714285
金蟲 (小有名氣)
- 數(shù)學EPI: 2
- 應助: 0 (幼兒園)
- 金幣: 890.9
- 帖子: 94
- 在線: 23.9小時
- 蟲號: 929249
- 注冊: 2009-12-16
- 專業(yè): 應用數(shù)學方法
★ ★
javeey(金幣+2):謝謝提供解釋 2010-04-16 19:35
javeey(金幣+2):謝謝提供解釋 2010-04-16 19:35
|
我來解釋 線性規(guī)劃，是運籌學中的較為成熟，應用較多的一個模型。 對一組非負變量Xi ， 在滿足一組關于Xi 的線性方程（稱為約束方程）的條件下， 求使得“關于Xi 的線性函數(shù) c(x)” 取得極大值或極小值的 特解問題。 稱為線性規(guī)劃問題。 （線性條件極值問題） 線性規(guī)劃模型的解法，在運籌中研究得較成功。 （解法不成問題），而實際問題，怎樣化為一個線性規(guī)劃問題，就是所謂建立線性規(guī)劃模型，并利用線性規(guī)劃模型的算法去解決實際問題，這才是應用者所關心的問題。 （解法的研究，是另一個領域，也還有很多研究者在不斷探索） 本例敘述將裝糖塊問題化為線性規(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， 所以它們加起來應該為1， 第i號 糖塊也是如此。所以有m個方程。 第二組約束方程是，每個袋子頂多裝M克， 以1號袋子為例，假設最優(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點較為精彩。題目要求是，使袋子盡可能少。 “造一個關于X（i,j）的線性函數(shù)，體現(xiàn)使袋子盡可能少�！� 事實是，因為糖塊總數(shù)是m, 所以每個袋子中最多裝m塊糖，不會比m多。 我們構造了每個袋子中糖塊數(shù)這一中間過程函數(shù)，f(j)=Σ X(i,j) （對于每個袋子求和） f(j) 的值域是0到m的整數(shù)。 用這些袋子糖塊數(shù)共同構造m+1進制數(shù)字的想法，可以發(fā)現(xiàn)，用袋子最少將對應m+1進制數(shù)的最小。 |
5樓2010-04-16 19:17:38
zhixian-ma
木蟲 (正式寫手)
- 應助: 54 (初中生)
- 金幣: 2568.7
- 散金: 51
- 紅花: 11
- 帖子: 894
- 在線: 123.2小時
- 蟲號: 965838
- 注冊: 2010-03-09
- 性別: GG
- 專業(yè): 傳熱傳質學
6樓2010-04-17 12:25:58
★
小木蟲(金幣+0.5):給個紅包，謝謝回帖交流
小木蟲(金幣+0.5):給個紅包，謝謝回帖交流
 |
7樓2010-09-12 00:38:50
 |
8樓2010-10-30 13:00:44
9樓2011-04-24 12:13:44
相關版塊跳轉
我要訂閱樓主 lizh714285 的主題更新
| 9 | 1/1 | 返回列表 |
| 最具人氣熱帖推薦 [查看全部] | 作者 | 回/看 | 最后發(fā)表 | |
|---|---|---|---|---|
|
[考研] 311求調(diào)劑 +3 | 希望上岸阿小楊 2026-03-23 | 3/150 |
|
|---|---|---|---|---|
|
|
[考研] 085404求調(diào)劑，總分309，本科經(jīng)歷較為豐富 +4 | 來財aa 2026-03-25 | 4/200 |
|
|
|
[考研] 291求調(diào)劑 +13 | hhhhxn.. 2026-03-23 | 19/950 |
|
|
[考研] 材料292調(diào)劑 +12 | 橘頌思美人 2026-03-23 | 12/600 |
|
|
|
[考研] 287求調(diào)劑 +10 | land xuxu 2026-03-26 | 10/500 |
|
|
|
[考研] 085600，材料與化工321分，求調(diào)劑 +9 | 大饞小子 2026-03-27 | 9/450 |
|
|
|
[考研] 求調(diào)劑，一志愿 南京航空航天大學大學 ，080500材料科學與工程學碩 +4 | @taotao 2026-03-26 | 5/250 |
|
|
|
[考研] 081200-11408-276學碩求調(diào)劑 +3 | 崔wj 2026-03-26 | 3/150 |
|
|
|
[考研] 一志愿華理，數(shù)一英一285求A區(qū)調(diào)劑 +8 | AZMK 2026-03-25 | 10/500 |
|
|
|
[考研] 0703化學求調(diào)劑 +3 | 丹青奶蓋 2026-03-26 | 5/250 |
|
|
|
[考研] 生物學學碩，一志愿湖南大學，初試成績338 +4 | YYYYYNNNNN 2026-03-26 | 4/200 |
|
|
|
[考研] 一志愿北京化工大學材料與化工（085600）296求調(diào)劑 +9 | 稻妻小編 2026-03-26 | 9/450 |
|
|
|
[考研] 334分 一志愿武理 材料求調(diào)劑 +4 | 李李不服輸 2026-03-26 | 4/200 |
|
|
|
[考研] 一志愿河工大 081700 276求調(diào)劑 +4 | 地球繞著太陽轉 2026-03-23 | 4/200 |
|
|
|
[考研] 263求調(diào)劑 +6 | yqdszhdap－ 2026-03-22 | 10/500 |
|
|
|
[考研] 【2026考研調(diào)劑】制藥工程 284分 求相關專業(yè)調(diào)劑名額 +4 | 袁奐奐 2026-03-25 | 8/400 |
|
|
|
[考研] 上海電力大學材料防護與新材料重點實驗室招收調(diào)劑研究生（材料、化學、電化學，環(huán)境） +4 | 我愛學電池 2026-03-23 | 4/200 |
|
|
|
[考研] 調(diào)劑 +4 | 13853210211 2026-03-24 | 4/200 |
|
|
|
[考研] 307求調(diào)劑 +3 | 余意卿 2026-03-21 | 6/300 |
|
|
|
[考研] 277分求調(diào)劑，跨調(diào)材料 +3 | 考研調(diào)劑lxh 2026-03-24 | 3/150 |
|