Greedy:Packets(POJ 1017)

　　　　　　　　　　　　　　装箱问题1.0

　　题目大意：就是一个工厂制造的产品都是正方形的，有1*1，2*2，3*3，4*4，5*5，6*6，高度都是h，现在要包装这些物品，只能用6*6*h的包装去装，问你怎么装才能使箱子打到最小？

　　这一题其实很简单，装箱子问题一般都是贪婪算法，这一题也不例外，那么这一又要怎么贪心呢？其实可以这样，我们可以看到，如果我们装了6,5,4这三个尺寸的物品，那么这个一个箱子肯定只能最大装这三个物品一个，6尺寸箱子没有空余位置，5尺寸的箱子还有11个空位，可以装11个1尺寸的物品，4尺寸的箱子可以再装5个2尺寸的物品。

　　但是3尺寸的物品就是有点复杂了，因为我们想尽量让三尺寸的物品装在一个箱子里面（贪婪嘛），我们知道一个箱子最多只能转4个三尺寸物品，如果三尺寸物品刚好为4的倍数，那么我们就可以得到箱子的个数了，如果剩余一个3尺寸物品，那么其中3尺寸箱子中的一个箱子还可以装5个2尺寸物品，如果剩余两个，则有3尺寸物品的箱子还可以装3个2尺寸物品，如果剩余3个，则那个3尺寸箱子还可以装1一个2尺寸物品。

　　我们只用把2尺寸的物品装好了，那么接下来的事情就简单了，前面我们在3,4尺寸的物品的时候解决了2尺寸物品的问题的一部分，最后剩下的2尺寸物品则有多少就放多少就可以了，1尺寸的填充剩下的，不够再放

　　这一题可以用模拟，不过太慢了，直接用数学去解就很快了

 #include <iostream>

 #include <functional>

 #include <algorithm>

 using namespace std;

 static int stuff[];

 static int left_3[] = { , , ,  };

 void Search(void);

 int main(void)

 {

     while ()

     {

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

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

         if (stuff[] ==  && stuff[] ==

             && stuff[] ==  && stuff[] ==

             && stuff[] ==  && stuff[] == )

             break;//6个物品为0，直接再见

         Search();

     }

     return ;

 }

 void Search(void)

 {

     int ans = , left_2, left_1;

     ans += stuff[] + stuff[] + stuff[] + (stuff[] + ) / ;//654肯定是有多少个加多少个,stuff[3] + 3向上取整

     left_2 = stuff[] *  + left_3[stuff[] % ];//如果这些箱子都填满了2*2的箱子

     if (left_2 < stuff[])

         ans += (stuff[] - left_2 + ) / ;

     left_1 =  * ans -  * stuff[] -  * stuff[] -  * stuff[]

         -  * stuff[] -  * stuff[];//在除了1*1的物品填满以后，剩余位置，向上取整

     if (left_1 < stuff[])

         ans += (stuff[] - left_1 + ) / ;//直接计算多出来1的大小，向上取整

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

 }

巴特西

Greedy:Packets(POJ 1017)

最新文章

热门文章