CubePacking的题意是这样的，有Ns个1*1*1和Nb个L*L*L的立方体，对这些立方体打包，要求正交放置，问说最小用多大的长方体盒子，思路是枚举盒子，然后把东西往里放。
枚举就是要去除那些重复的项，即枚举满足x<=y<=z且x*y*z<=n的(x,y)，这个的复杂度说是只有O(N^(2/3))，那样的话对于N是INT_MAX的话，也是可以接受的。然后放置那些立方体，求最小的高，复杂度是O(1)，方法是让那些L*L*L的立方体组成长方体的样子贪心放置，然后剩下的填充进去。
比较难想到的是，要去枚举那个盒子，说是根据盒子的大小是有个上界这一条想到的。上述的算法复杂度平摊分析还不会，代码如下：
#include <iostream> #include <string> using namespace std; typedef long long int64; int getMinZ(int Ns, int Nb, int L, int x, int y) //x <= y <= z { if(x < L || y < L) return INT_MAX; int nx = x / L, ny = y / L; int leftS = x * y - nx * ny * L * L; int h = (Nb + nx * ny - 1) / (nx * ny); int leftL = Nb % (nx * ny); if(leftL) leftL = nx * ny - leftL; int leftM = Ns - leftL * L * L * L; leftM = max(leftM, 0); leftM -= leftS * h * L; leftM = max(leftM, 0); return (leftM + x * y - 1) / (x * y) + h * L; } int go(int Ns, int Nb, int L) { int n = INT_MAX; int res = n; for(int x = 1; (int64)x * x * x <= n; x++) { for(int y = x; (int64)x * y * y <= n; y++) { int min_z = getMinZ(Ns, Nb, L, x, y); res = min((int64)res, (int64)x * y * min_z); } } return res; } class CubePacking { public: int getMinimumVolume(int Ns, int Nb, int L) { return go(Ns, Nb, L); } };转载于:https://www.cnblogs.com/litstrong/archive/2011/06/20/2085134.html
相关资源：数据结构—成绩单生成器