POJ 1017 Packet

http://poj.org/problem?id=1017

有1*1 2*2...6*6的物品 要装在 6*6的parcel中 问最少用多少个parcel

一直没有找到贪心的策略

问题应该出现在 总是在想怎么放入parcel中 使得最节省空间

其实这种角度是很麻烦的 情况太多 很难描述清楚

但是其实 放一类型物品 得到的结果是非常具体的

-->>>即从要放的东西的角度出发

放 一个6*6 物品 会占用一个parce

放 一个5*5 物品 会占用一个parce 并且空出11个1*1的空位

放 一个4*4 物品 会占用一个parce 并且空出5个2*2的空位(可以转化为1*1的空位)

放3*3

：放一个 空出 5个2*2的空位 和7个1*1的空位

：放两个 空出 3个2*2的空位 和6个1*1的空位

：放三个 空出 1个2*2的空位 和5个1*1的空位

1*1 和 2*2 的物品作用是用来填补空位的

如果空位被填满 但是物品还未放完　　就要再开一个新的parcel

2*2的物品放完后 将所有2*2的空位 变成 1*1的空位

 #include <iostream>

 #include <string.h>

 #include <stdio.h>

 using namespace std;

 //从 六种要装的物品考虑 装每一种物品会空出的空格的情况

 int num[];

 int main()

 {

     freopen("in.txt", "r", stdin);

     int temp = ;

     int parcel = ;

     int space[];

     while (~scanf("%d", &num[]))

     {

         temp = ;

         temp |= num[];

         memset(space, , sizeof(space));

         parcel = ;

         for (int i = ; i < ; i++)

         {

             scanf("%d", &num[i]);

             temp |= num[i];

         }

         if (!temp) break;

         parcel = num[] + num[] + num[];

         space[] = num[] * ;//先解决 6*6,5*5,4*4 的包装盒

         space[] = num[] * ;

         //解决3*3的盒子

         int p3 = , remain = ;

         remain = num[] % ;

         p3 = remain ? (num[]/)+ : num[]/;//如果还有剩余就多开一个盒子

         parcel += p3;

         switch(remain)//剩下多少个3*3的物品

         {

             case : space[] += ; space[] += ;break;

             case : space[] += ; space[] += ;break;

             case : space[] += ; space[] += ;break;

         }

         //然后解决 2*2 的盒子

         remain = min(num[], space[]);

         num[] -= remain;

         space[] -= remain;

         space[] += space[] * ;

         if (num[])

         {

             remain = num[] % ;

             if (remain)//如果还有剩余就多开一个盒子

             {

                 parcel += num[] /  + ;

                 space[] += *(-remain);

             }

             else

             {

                 parcel += num[] / ;

             }

         }

         //解决1*1

         num[] -= min(num[], space[]);

         if (num[])

         {

             remain = num[] % ;

             parcel += remain ? num[] /  +  : num[] / ;//如果还有剩余就多开一个盒子  后面两个逻辑不严密 没有考虑清楚而出错

         }

         printf("%d\n", parcel);

     }

     return ;

 }