| 查看: 1139 | 回复: 8 | |||
lizh714285金虫 (小有名气)
|
[交流]
【趣题鉴赏】最少需要几个袋子？已有3人参与
|
|
转自“博士数学论坛”的一个帖子 (转载理由：4楼建的01规划模型很巧妙，尤其是目标函数的设置方法，值得推荐) 1# 最少需要几个袋子？ 有一堆糖块N克，总共m块，分别重a1,a2,a3,.....am克， 现有最多能装M克的袋子足够多个，M>= max{a1,a2,a3,a4....am} 请问最少需要几个袋子才能把所有的糖装完？ 最好能给出方法！补充：所给的袋子都是一样的。 ------------------------------------------------------------------------------------ 2# 定义：某几个糖块组成的一个集合A，如果这几个糖块的质量之和小于M，则称A为一个候选。找出包含a1的所有候选，找出包含a2的所有候选，…，找出包含am的所有候选。取这些候选中质量最大的装入一个袋子中。继续以上的步骤，在有限步内即可把所有的糖块都装完。 ------------------------------------------------------------------------------------ 3# 首先把所有糖块按照重量由大到小排列，不妨设为a01,a02,a03,……,a0m，然后 （1）将目前最重放入袋B1中， （2）看剩下糖块中最重的能否能放入B1中，如果能重复（2），如果不能则判断能不能放入下一个袋子中，如果能重复（2）,否则取新袋子装，后重复（2），直至所有糖块都装入袋子中。 ------------------------------------------------------------------------------------ 4# 这可以使用线性规划模型(01规划)来求解。 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）目标函数，要使袋子尽可能少； 取函数f(j)=Σ X(i,j) （说明，和号下为i=1,和号上为m）， 该函数表述了j号袋子中的糖块数量. 由于每个袋子中的糖块可能是0，1，2，....m个； 所以f(j) 取系数1， m+1, (m+1)^2, (m+1)^3， ......, (m+1)^（m-1） ; （共m个系数）；命名为c(1),c(2),。。。c(m) 目标函数为 Σ c(j) * f(j) 显然这是一个关于决策变量X(i,j)的线性函数 ； 目标函数最小化；（由于更靠后的袋子中的每个糖块，其权重是相邻前一个袋子权重的m+1倍，按m+1进制计数自然数，用几个袋子则对应几位整数 （例如，用4个袋子，对应目标函数为m+1进制的4位数）；不难证明这个目标函数确有引导袋子最小化的作用）。 6）初始可行解， X(i,i)=1 , X(i,j)=0(对i不等于j) 7) 运算结果，获得了一个装糖块的最优方案，不但回答了楼主的问题，而且给出了装糖果的具体方案 _________________________________________ |
回复此楼» 猜你喜欢
之前让一硕士生水了7个发明专利，现在这7个获批发明专利的维护费可从哪儿支出哈？
已经有3人回复
-
到新单位后，换了新的研究方向，没有团队，持续积累2区以上论文，能申请到面上吗
已经有12人回复
-
博士读完未来一定会好吗
已经有27人回复
-
投稿精细化工
已经有4人回复
-
高职单位投计算机相关的北核或SCI四区期刊推荐，求支招！
已经有4人回复
-
导师想让我从独立一作变成了共一第一
已经有9人回复
-
读博
已经有4人回复
-
JMPT 期刊投稿流程
已经有4人回复
-
心脉受损
已经有5人回复
-
Springer期刊投稿求助
已经有4人回复
» 本主题相关价值贴推荐，对您同样有帮助:
一个副高带几个学生的团队申面上是不是薄弱了？
已经有21人回复- 小弟的本硕学历学位证书都丢了（放在一个袋子里丢得），有木有办法补呢
已经有9人回复
- 女生，华南理工博士复试，需要穿正装吗？
已经有24人回复
- 【求助/交流】细菌同源重组的同源臂最少需要多少bp呢？
已经有7人回复
- 【求助】下半年加拿大访问学者，想申请csc，需要自己办签证吗
已经有8人回复
- 【活动】你每天用几只塑料袋？不论大小
已经有42人回复
- 【求助】求助透析袋子的使用问题。
已经有3人回复
zengpeiwei
金虫 (著名写手)
- 应助: 0 (幼儿园)
- 金币: 93.4
- 红花: 1
- 帖子: 1033
- 在线: 355小时
- 虫号: 853973
- 注册: 2009-09-22
- 性别: GG
- 专业: 有机合成
2楼2010-04-14 19:40:46
3楼2010-04-16 13:05:21
4楼2010-04-16 15:33:51
lizh714285
金虫 (小有名气)
- 数学EPI: 2
- 应助: 0 (幼儿园)
- 金币: 890.9
- 帖子: 94
- 在线: 23.9小时
- 虫号: 929249
- 注册: 2009-12-16
- 专业: 应用数学方法
★ ★
javeey(金币+2):谢谢提供解释 2010-04-16 19:35
javeey(金币+2):谢谢提供解释 2010-04-16 19:35
|
我来解释 线性规划，是运筹学中的较为成熟，应用较多的一个模型。 对一组非负变量Xi ， 在满足一组关于Xi 的线性方程（称为约束方程）的条件下， 求使得“关于Xi 的线性函数 c(x)” 取得极大值或极小值的 特解问题。 称为线性规划问题。 （线性条件极值问题） 线性规划模型的解法，在运筹中研究得较成功。 （解法不成问题），而实际问题，怎样化为一个线性规划问题，就是所谓建立线性规划模型，并利用线性规划模型的算法去解决实际问题，这才是应用者所关心的问题。 （解法的研究，是另一个领域，也还有很多研究者在不断探索） 本例叙述将装糖块问题化为线性规划问题的建模过程。 第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号袋子为例，假设最优解中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）的线性函数，体现使袋子尽可能少。” 事实是，因为糖块总数是m, 所以每个袋子中最多装m块糖，不会比m多。 我们构造了每个袋子中糖块数这一中间过程函数，f(j)=Σ X(i,j) （对于每个袋子求和） f(j) 的值域是0到m的整数。 用这些袋子糖块数共同构造m+1进制数字的想法，可以发现，用袋子最少将对应m+1进制数的最小。 |
5楼2010-04-16 19:17:38
zhixian-ma
木虫 (正式写手)
- 应助: 54 (初中生)
- 金币: 2568.7
- 散金: 51
- 红花: 11
- 帖子: 894
- 在线: 123.2小时
- 虫号: 965838
- 注册: 2010-03-09
- 性别: GG
- 专业: 传热传质学
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