24小时热门版块排行榜

返回列表

当前只显示满足指定条件的回帖，点击这里查看本话题的所有回帖

lizh714285

金虫 (小有名气)

数学EPI: 2
应助: 0 (幼儿园)
金币: 890.9
帖子: 94
在线: 23.9小时
虫号: 929249
注册: 2009-12-16
专业: 应用数学方法

[交流] 【趣题鉴赏】最少需要几个袋子？已有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) 运算结果，获得了一个装糖块的最优方案，不但回答了楼主的问题，而且给出了装糖果的具体方案

_________________________________________

回复此楼