论坛 › 小题大作 › 卡车运货

gxqcn 发表于 2014-2-9 10:01:47

卡车运货

\( 36 \) 吨货物分装在一批箱子里，箱子本身质量极轻，每箱所装货物都不超过 \( 1 \) 吨，
证明：可用 \( 11 \) 辆核载为 \( 4 \) 吨的卡车一次性运走该批货物（并请给出可行方案）。

注：箱子尺寸都不大，在不超载的前提下，不会导致卡车超宽超高问题。

gxqcn 发表于 2014-2-9 20:17:20

这是一道小智力题，比较适合给小学生做。

如果箱子所装货物本身正好是 \( 1 \) 吨，或者若干个均可凑成 \( 1 \) 吨，则仅需 \( 36/4=9 \) 辆车即可。
假如没有这么凑巧的话，不管怎样，每辆卡车至少可拉 \( 3 \) 吨货物，\( \left\lceil\dfrac{36}{4-1} \right\rceil=12 \) 辆肯定是足矣的。
现在只提供 \( 11 \) 辆，怎么做？

我们先安排 \( 8 \) 辆卡车装车，尽可能地装，直到超载时，取下最后那个货箱放置在车旁待命，
则每辆车上连同车旁的箱子里总货物一定大于等于 \( 4 \) 吨，余下不超过 \( (36-4*8=4) \) 吨的货物，第 \( 9 \) 辆车可以全部装下了。

现在还剩两辆车，及 \( 8 \) 个箱子，每个车分装 \( 4 \) 个箱子，同样也绝对不会超载。
至此，所有货物装车完毕，且各车都在核载范围内，可以浩浩荡荡出发了。

hujunhua 发表于 2014-2-10 16:56:46

很妙。貌似 \( 11 \) 车很宽松，但是容易证明 \( 10 \) 车不是总够。当每箱为 \(0.88\) 吨时，共 \( 41 \) 箱，一车只能装 \( 4 \) 箱， \( 10 \) 车不够。

gxqcn 发表于 2014-2-10 19:49:41

这道题关键是给出合理可行的方案，且要严谨。

类似的题，网上不少人居然给出解答 \( 10 \) 辆就可以了，比如：一道数学题 和 http://zhidao.baidu.com/question/409702140.html
楼上的例子同样非常巧妙地反驳了他们。

hujunhua 发表于 2014-2-12 01:23:43

当每箱为\(0.878\)吨时，共 \(41\) 箱，一车只能装 \(4\) 箱， \(10\) 车不够。
当每箱为\(0.857\)吨时，共 \(42\) 箱，一车只能装 \(4\) 箱， \(10\) 车不够。
当每箱为\(0.837\)吨时，共 \(43\) 箱，一车只能装 \(4\) 箱， \(10\) 车不够。
当每箱为\(0.818\)吨时，共 \(44\) 箱，一车只能装 \(4\) 箱， \(11\) 车刚好。
当每箱为\(0.706\)吨时，共 \(51\) 箱，一车只能装 \(5\) 箱， \(10\) 车不够。
当每箱为\(0.692\)吨时，共 \(52\) 箱，一车只能装 \(5\) 箱， \(10\) 车不够。
当每箱为\(0.679\)吨时，共 \(53\) 箱，一车只能装 \(5\) 箱， \(10\) 车不够。
当每箱为\(0.590\)吨时，共 \(61\) 箱，一车只能装 \(6\) 箱， \(10\) 车不够。
当每箱为\(0.581\)吨时，共 \(62\) 箱，一车只能装 \(6\) 箱， \(10\) 车不够。
当每箱为\(0.507\)吨时，共 \(71\) 箱，一车只能装 \(7\) 箱， \(10\) 车不够。

wayne 发表于 2014-2-12 08:57:02

每个箱子 \( 1\) 吨,总共 \( 36 \) 个箱子.每车\(4\)箱子, 总共 \(9\)车即可拖走.
每个箱子 \( 0.8 \) 吨,总共 \( 45 \) 个箱子.每车\(5\)箱子, 总共 \(9\)车即可拖走.
每个箱子 \( 0.72 \) 吨,总共 \( 50 \) 个箱子.每车\(5\)箱子, 总共 \(10\)车即可拖走.

wayne 发表于 2014-2-12 09:18:02

问题的本质是箱子是整数, 箱子载重$x$是实数. 所以,从箱子个数入手,最简洁.
比如,$10$车,有$a$车$5$个箱子,$10-a$车$4$个箱子,那么每个箱子载重不超过$4$吨,则$5x<=4$
同时,$(5a+4(10-a))*x=36$ ,即$5<=a<=9,5$种装箱方式均可,只是每种情况下,箱子载重$x=36/{40+a}$

wayne 发表于 2014-2-12 11:29:44

当然直接从箱子载重 \( x \) 入手也可以。 解方程\( kx \le 4 < (k+1)x \quad \And \quad 9kx≤36<10kx, \quad k \in \NN, k\ge4 \)得到
\( \max\left( \dfrac4{k+1},\dfrac{36}{10+k} \right)<x≤\dfrac4k \)
箱子载重 \(x\) 的合理区间是
{0.90000, 1.0000}
{0.72000,0.80000}
{0.60000,0.66667}
{0.51429,0.57143}
{0.45000,0.50000}
{0.40000,0.44444}
{0.36364,0.40000}
{0.33333,0.36364}
{0.30769,0.33333}
{0.28571,0.30769}
{0.26667,0.28571}
{0.25000,0.26667}
{0.23529,0.25000}
{0.22222,0.23529}
{0.21053,0.22222}
{0.20000,0.21053}
{0.19048,0.20000}
5#列出的“10车不够” 均不在这些区间内.

gxqcn 发表于 2014-2-13 21:32:45

更一般的问题：
总质量为 \( T \) 吨的货物分装在一批箱子里，箱子本身质量极轻，每箱所装货物都不超过 \( 1 \) 吨，
则可至少需要多少辆核载为 \( p \) 吨 \( (p>1) \) 的卡车，以确保可一次性运走该批货物？

令 \( r=\dfrac{p}{+1} \)，则有结论：
如果有若干个箱子货物总质量超过 \( p \) 吨（每个不超过 \( 1 \) 吨），
按先重后轻顺序装车，总能在核载为 \( p \) 吨的卡车上装上比 \( (p-r) \) 吨多的货物。
\( \therefore \) 至少需要的辆数 \( n=\left\lceil \dfrac{T-r}{p-r} \right\rceil \)（向上取整）。

如果每箱所装货物上限不是 \( 1 \) 吨，比如是 \( t \) 吨（ \( t<p \) ），
我们可以把 \( t \) 吨看作是“\( 1 \) 个质量单位”，将 \( T,p \) 各自先除以 \( t \) 后即可用上述结论。
或者仅更改 \( r \) 的定义为：\( r=\dfrac{p}{\left[ \dfrac p t \right]+1} \)，其它公式则可保持不变。

纷飞冷雨 发表于 2015-6-21 11:09:23

#include "stdio.h"
#include "stdlib.h"
main()
{ int i,n,m; float t;
int a1,a2,a3,a4,a5,a6,a7,a8,a9,a10,a11;       
FILE *fp;
        if((fp=fopen("data1.txt","w+"))==NULL)
        {printf("Can not open file\n");
       exit(0);
        }
      
        for(t=0.001;t<=1;t=t+0.001)/*t为每箱重量，以1kg为步进，到1吨为止，遍历所有的箱重可能*/
        {n=(int)(36/t);/*n为货物总的箱子数量*/
       m=(int)(4/t);/*m为一辆车最多能装的箱子数量*/
       fprintf(fp,"n=%d,m=%d\n",n,m);
                for(a1=1;a1<=m;a1++)/*a1-a11为每辆车的编号，从1箱到m箱尝试*/
                for(a2=0;a2<=m;a2++)
                for(a3=0;a3<=m;a3++)
                for(a4=0;a4<=m;a4++)
                for(a5=0;a5<=m;a5++)
                for(a6=0;a6<=m;a6++)
                for(a7=0;a7<=m;a7++)
                for(a8=0;a8<=m;a8++)
                for(a9=0;a9<=m;a9++)
                for(a10=0;a10<=m;a10++)
                for(a11=0;a11<=m;a11++)
                  if((a1+a2+a3+a4+a5+a6+a7+a8+a9+a10+a11)==n)
                  {        fprintf(fp,"t=%f\n",t);
                        i++;/*i记录答案的个数*/
                        fprintf(fp,"%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d\n\n",a1,a2,a3,a4,a5,a6,a7,a8,a9,a10,a11);
                  }
        }fprintf(fp,"i=%d",i);
       fclose(fp);
}
   不得不说这个算法的计算量实在太大，在2.7GHz的pentium g630上计算20分钟无果。
   然后我只能指定每箱重0.507吨时的情况。
#include "stdio.h"
#include "stdlib.h"
main()
{ int i,n,m; float t;
int a1,a2,a3,a4,a5,a6,a7,a8,a9,a10,a11;       
FILE *fp;
        if((fp=fopen("data1.txt","w+"))==NULL)
        {printf("Can not open file\n");
       exit(0);
        }
         t=0.507;
       
       n=(int)(36/t);
       m=(int)(4/t);
       fprintf(fp,"n=%d,m=%d\n",n,m);
                for(a1=1;a1<=m;a1++)
                for(a2=0;a2<=m;a2++)
                for(a3=0;a3<=m;a3++)
                for(a4=0;a4<=m;a4++)
                for(a5=0;a5<=m;a5++)
                for(a6=0;a6<=m;a6++)
                for(a7=0;a7<=m;a7++)
                for(a8=0;a8<=m;a8++)
                for(a9=0;a9<=m;a9++)
                for(a10=0;a10<=m;a10++)
                for(a11=0;a11<=m;a11++)
                  if((a1+a2+a3+a4+a5+a6+a7+a8+a9+a10+a11)==n)
                  {        i++;
                        fprintf(fp,"%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d\n\n",a1,a2,a3,a4,a5,a6,a7,a8,a9,a10,a11);
                  }
        fprintf(fp,"i=%d",i);
       fclose(fp);
}
当每箱重0.507吨时，有2301572种组合，难怪会有这么大的计算量。


n=71,m=7
t=0.507000
1,7,7,7,7,7,7,7,7,7,7

t=0.507000
2,6,7,7,7,7,7,7,7,7,7

t=0.507000
2,7,6,7,7,7,7,7,7,7,7

t=0.507000
2,7,7,6,7,7,7,7,7,7,7

t=0.507000
2,7,7,7,6,7,7,7,7,7,7

t=0.507000
2,7,7,7,7,6,7,7,7,7,7

t=0.507000
2,7,7,7,7,7,6,7,7,7,7

t=0.507000
2,7,7,7,7,7,7,6,7,7,7



补充内容 (2015-10-24 23:14):
程序第四行应改为int i=0,n,m; float t;
计算结果为:每箱重0.507吨时,有8008种组合.

查看完整版本: 卡车运货