首页 › 题库 › C/C++编程考级 › C/C++编程五级 › 简答题
简答题 偏难
#7430

装箱问题 一个工厂制造的产品形状都是长方体,它们的高度都是h,长和宽都相等,一共有六个型号,他们的长宽分别为1*1, 2*2, 3*3, 4*4, 5*5, 6…

装箱问题

一个工厂制造的产品形状都是长方体,它们的高度都是h,长和宽都相等,一共有六个型号,他们的长宽分别为1*1, 2*2, 3*3, 4*4, 5*5, 6*6。这些产品通常使用一个 6*6*h 的长方体包裹包装然后邮寄给客户。因为邮费很贵,所以工厂要想方设法的减小每个订单运送时的包裹数量。他们很需要有一个好的程序帮他们解决这个问题从而节省费用。现在这个程序由你来设计。

时间限制:1000

内存限制:65536

输入

输入文件包括几行,每一行代表一个订单。每个订单里的一行包括六个整数,中间用空格隔开,分别为1*1至6*6这六种产品的数量。输入文件将以6个0组成的一行结尾。

输出

除了输入的最后一行6个0以外,输入文件里每一行对应着输出文件的一行,每一行输出一个整数代表对应的订单所需的最小包裹数。

样例输入

0 0 4 0 0 1 
7 5 1 0 0 0 
0 0 0 0 0 0

样例输出

2 
1
未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">//解法1:贪心 #include &lt;bits/stdc++.h&gt; using namespace std; int status[8][4];//status[i][j]:包裹中已有1个大小为i*i的产品,此时可以最多放入多少个j*j的产品  void initStatus() {//status[0]:包裹中没有产品时,各种产品最多可以放多少个      status[2][2] = 8;     status[3][2] = 5, status[3][3] = 3;     status[4][2] = 5;     for(int i = 1; i &lt;= 6; ++i)         status[i][1] = 36 - i*i; } int pro[8];//pro[i]:i*i产品的数量 int main()  {     initStatus();      while(true)     {         int sum = 0, bag = 0, rem[8];//sum:总产品数量  bag:包裹数 rem[i]:当前剩余空间能放几个i*i          for(int i = 1; i &lt;= 6; ++i)         {             cin &gt;&gt; pro[i];             sum += pro[i];         }         if(sum == 0)//如果6个数都是0,那么加和为0,要跳出循环              break;         for(int i = 6; i &gt;= 1; --i)         {             while(pro[i] &gt; 0)             {                 bag++;//用一个新包裹放i*i                 pro[i]--;                 for(int j = 1; j &lt;= 3; ++j)//获取当前剩余空间情况                      rem[j] = status[i][j];                 int j = 3;                 while(j &gt;= 1)                 {                     if(rem[j] &gt; 0 &amp;&amp; pro[j] &gt; 0)//如果可以放j*j的产品                      {                         pro[j]--;//放一个产品                          if(j == 3)                         {                             rem[3]--;                             rem[2] -= 2;                             rem[1] -= 9;                         }                         else if(j == 2)                         {                             rem[2]--;                             rem[1] -= 4;                         }                         else//j == 1                             rem[1]--;                     }                     else                         --j;                 }             }            }         cout &lt;&lt; bag &lt;&lt; endl;     }       return 0; }</pre><pre class="brush:cpp;toolbar:false">//解法2:手动完成贪心过程 #include&lt;bits/stdc++.h&gt; using namespace std; int bag;//总包裹数  int k[4] = {0, 5, 3, 1};//k[i]表示3*3的产品有i个时(k[0]表示有4个时)剩余空间可以放2*2产品的个数    int pro[8], p2, p1;//p2:2*2空位数 p1:1*1空位数  int main() {      while(true)     {         for(int i = 1; i &lt;= 6; ++i)             cin &gt;&gt; pro[i];       if(pro[1] == 0 &amp;&amp; pro[2] == 0 &amp;&amp; pro[3] == 0 &amp;&amp; pro[4] == 0 &amp;&amp; pro[5] == 0 &amp;&amp; pro[6] == 0)              break;       bag = pro[6] + pro[5] + pro[4] + ceil(pro[3]/4.0);//6*6和5*5和4*4一定是一个占一个箱子,而3*3 4个占一个箱子         p2 = 5*pro[4]+k[pro[3]%4];//k[pro[3]%4]:有pro[3]%4个3*3在一个包裹中时,剩下的位置可以放2*2的数目         if(pro[2] &gt; p2)//2*2的个数比我们留出来为2*2的空间个数多,就需要为2*2另开箱子             bag += ceil((pro[2]-p2)/9.0);//多出来的2*2箱子应该占用的新箱子数        p1 = 36*bag-36*pro[6]-25*pro[5]-16*pro[4]-9*pro[3]-4*pro[2];//求出当前包裹中所有剩下的可以放1*1的位置数          if(pro[1] &gt; p1)//如果1*1的个数,比我们留出的空间多就需要另开空间         bag += ceil((pro[1]-p1)/36.0);//将多出来的另开箱子      cout &lt;&lt; bag &lt;&lt; endl;     }     return 0; }</pre><pre class="brush:cpp;toolbar:false">//解法3: #include&lt;iostream&gt; #include&lt;cstdio&gt; #include&lt;cstdlib&gt; #include&lt;cstring&gt; #include&lt;algorithm&gt; #define INF 999999999 #define N 101 using namespace std;   int main() {     int a,b,c,d,e,f;     int g[4]={0,5,3,1};     int x,y;       while(cin&gt;&gt;a&gt;&gt;b&gt;&gt;c&gt;&gt;d&gt;&gt;e&gt;&gt;f)     {         if(a+b+c+d+e+f==0)             break;         int n=f+e+d+(c+3)/4;         x=5*d+g[c%4];         if(b&gt;x)             n+=(b-x+8)/9;         y=36*n-36*f-25*e-16*d-9*c-4*b;         if(a&gt;y)             n+=(a-y+35)/36;         cout&lt;&lt;n&lt;&lt;endl;     }     return 0; }</pre><p><br/></p>
这道题暂未补解析。