很有挑战性的算法问题，一下子应该做不出来，希望大家五一加油，如果能解答，巨分相送
有一个大箱子长宽高分别是60，40，80，并且有如下物品
名称 长宽高 数量
物品1 10，5，6 8
物品2 8，6，8 3
物品3 5，8，6 7
物品4 6，8，9 10
物品5 3，5，9 16
问题是，在这个有限的箱子中，如何摆放这些东西，每样产品放多少，可以放的物品最多？
[解决办法]
有意思, 分是我的啦.
[解决办法]
mark 到时候看看能不能解决
[解决办法]
mark.
[解决办法]
kankan
[解决办法]
mark
[解决办法]
有意思 五一带回家做去 现在没时间
[解决办法]
这是个很出名的问题吧,记得我以前学习教材上也提到这个问题.
[解决办法]
喜欢挑战
[解决办法]
mark
[解决办法]
挺有意思的！
仔细想想！
[解决办法]
接受挑战! 哈
[解决办法]
此问题有歧义，是放的数量最多，还是尽量多放（空闲空间最少）？
算法思想差不多，但是差异也很大。
[解决办法]
有点像装箱问题。
[解决办法]
这个应该属于背包问题的扩展吧。
[解决办法]
这个数据不是很好
箱子总容量：192000
物品总体积： 11712
结果很显然，不能真正考验算法的性能。
[解决办法]
背包问题
[解决办法]
mark
[解决办法]
mark
[解决办法]
大家可以去看“关于二维矩阵两点间步数计算的问题 ”吗？
[解决办法]
大家可以去看“关于二维矩阵两点间步数计算的问题 ”吗？我急用。最好15:50前，谢谢！
[解决办法]
这个数据不是很好
箱子总容量：192000
物品总体积： 11712
结果很显然，不能真正考验算法的性能。
[解决办法]
static int num=0;
class BOX
{
private:
double length;
double width;
double height;
int quantity;
double vol;
int seri
public:
double Vol(double plength,
double pwidth,
double pheight);
BOX(){}
BOX(double plength,
double pwidth,
double pheight,
int pquantity
double pvol)
{
length=plength;
width=pwidth;
height=pheight;
quantity=pquantity;
pvol=this.Vol(length,width,height);
seri=num++;
}
double Vol(double plength,
double pwidth,
double pheight)
{
return plength*pwidth*pheight;
}
};
void put(BOX *pbox,int n,BOX pVenter,int *ser)
{
int *ser=new int[n];//选择放的顺序的序号
double U=pVenter.vol;
for(int i=0;i <n;i++){
if(pbox[i].vol> U)break;
if(pbox[i].quantity> 1){
for(int t=0;t <pbox[i].quantity;t++)
ser[i+t]=pbox[i-1].num
}
ser[i]=pbox[i].num;
U-=pbox[i].vol;
}
if(i <n){
ser[i]=U/pbox[i].vol;
}
else{
for(;i <n;i++){
if(pbox[i].vol <U)
ser[i]=pbox[i].num;
}
delete[] ser;
/*位置？横着放？竖着放？等待高人*/
}
[解决办法]
// 由于箱子太大, 物品好象怎么放都可以
// 最差劲的算法: 随机选物品, 按顺序放置物品
// 程序没有仔细测试过, 可能有bug
#include <iostream>
#include <vector>
#include <set>
#include <ctime>
using namespace std;
struct Object
{
int length, width, height;
int id;
int catalog;
bool stacked;
int realL, realW, realH;
int x, y, z;
void init()
{
stacked = false;
x=y=z=-1;
realL=length, realW=width, realH=height;
}
void reShape(int way)
{
switch(way){
case 0:
realL = length;
realW = width;
realH = height;
break;
case 1:
realH = length;
realW = height;
realH = width;
break;
case 2:
realL = width;
realW = length;
realH = height;
break;
case 3:
realL = width;
realW = height;
realH = length;
break;
case 4:
realL = height;
realW = length;
realH = width;
break;
case 5:
realL = height;
realW = width;
realH = length;
break;
default:
break;
}
}
};
struct ObjectCompare
{
bool operator() (Object* const &obj1, Object* const &obj2)
{
if(obj1-> z < obj2-> z) return true;
else if(obj1-> z == obj2-> z)
if(obj1-> y < obj2-> y) return true;
else if(obj1-> y == obj2-> y)
if(obj1-> x < obj2-> x) return true;
return false;
}
};
class Box
{
int length, width, height;
int pieces;
set <Object*, ObjectCompare> items;
public:
Box(int l, int w, int h): length(l), width(w), height(h)
{
pieces = 0;
}
bool stackObject(Object *obj);
void withdrawObject(Object *obj);
bool intersect(Object *obj);
void print();
void reset()
{
pieces = 0;
items.clear();
}
};
// not used
void Box::withdrawObject(Object *obj)
{
return;
}
bool Box::stackObject(Object *obj)
{
int a, b, c;
// find the available space
// starting from the center
int x0 = 0;
int y0 = 0;
int z0 = 0;
if(pieces == 0) {
obj-> x = x0;
obj-> y = y0;
obj-> z = z0;
items.insert(obj);
pieces++;
return true;
}
set <Object*, ObjectCompare> ::iterator it;
for(it=items.begin(); it != items.end(); it++) {
x0 = (*it)-> x + (*it)-> realL+1;
y0 = (*it)-> y;
z0 = (*it)-> z;
obj-> x = x0;
obj-> y = y0;
obj-> z = z0;
if(intersect(obj)) return true;
x0 = (*it)-> x;
y0 = (*it)-> y + (*it)-> realW+1;
z0 = (*it)-> z;
obj-> x = x0;
obj-> y = y0;
obj-> z = z0;
if(intersect(obj)) return true;
x0 = (*it)-> x;
y0 = (*it)-> y;
z0 = (*it)-> z + (*it)-> realH+1;
obj-> x = x0;
obj-> y = y0;
obj-> z = z0;
if(intersect(obj)) return true;
}
// failed!
//print out the result
print();
return false;
}
void Box::print()
{
set <Object*, ObjectCompare> ::iterator it;
cout < < "Totally " < < pieces < < " pieces were stacked " < < endl;
cout < < "They are " < < endl;
for(it=items.begin(); it != items.end(); it++) {
cout < < "Item id: " < < (*it)-> id < < endl;
cout < < "Catagory: " < < (*it)-> catalog < < endl;
cout < < "Position at " < < (*it)-> x < < ", " < < (*it)-> y < < ", " < < (*it)-> z < < endl;
cout < < "Size " < < (*it)-> realL < < ", " < < (*it)-> realW < < ", " < < (*it)-> realH < < endl;
cout < < endl;
}
}
bool Box::intersect(Object* obj)
{
// first check if outbound
if(obj-> x + obj-> realL > length) return false;
if(obj-> y + obj-> realW > width) return false;
if(obj-> z + obj-> realH > height) return false;
set <Object*, ObjectCompare> ::iterator it;
for(it=items.begin(); it != items.end(); it++) {
bool b1 = obj-> x > = (*it)-> x && obj-> x <= (*it)-> x + (*it)-> realL;
bool b2 = obj-> x + obj-> realL > = (*it)-> x && obj-> x + obj-> realL <= (*it)-> x + (*it)-> realL;
bool b3 = obj-> y > = (*it)-> y && obj-> y <= (*it)-> y + (*it)-> realW;
bool b4 = obj-> y + obj-> realW > = (*it)-> y && obj-> y + obj-> realW <= (*it)-> y + (*it)-> realW;
bool b5 = obj-> z > = (*it)-> z && obj-> z <= (*it)-> z + (*it)-> realH;
bool b6 = obj-> z + obj-> realH > = (*it)-> z && obj-> z + obj-> realH <= (*it)-> z + (*it)-> realH;
if((b1 || b2 ) && (b3 || b4) && (b5 || b6)) return false;
}
// true!
// nowdo the insert
items.insert(obj);
pieces++;
return true;
}
int main()
{
Box box(60, 40, 80);
vector <Object *> objects;
const int p1=8, p2=3, p3=7, p4=10, p5=16;
Object obj1[p1];
for(int i=0; i <p1; i++) {
obj1[i].length =10;
obj1[i].width = 5;
obj1[i].height = 6;
obj1[i].id = i;
obj1[i].catalog = 1;
obj1[i].init();
objects.push_back(&obj1[i]);
}
Object obj2[p2];
for(int i=0; i <p2; i++) {
obj2[i].length =8;
obj2[i].width =6;
obj2[i].height = 8;
obj2[i].id = i+p1;
obj2[i].catalog = 2;
obj2[i].init();
objects.push_back(&obj2[i]);
}
Object obj3[p3];
for(int i=0; i <p3; i++) {
obj3[i].length =5;
obj3[i].width = 8;
obj3[i].height = 6;
obj3[i].id = i+p1+p2;
obj3[i].catalog = 3;
obj3[i].init();
objects.push_back(&obj3[i]);
}
Object obj4[p4];
for(int i=0; i <p4; i++) {
obj4[i].length =6;
obj4[i].width = 8;
obj4[i].height = 9;
obj4[i].id = i+p1+p2+p3;
obj4[i].catalog = 4;
obj4[i].init();
objects.push_back(&obj4[i]);
}
Object obj5[p5];
for(int i=0; i <p5; i++) {
obj5[i].length =3;
obj5[i].width = 5;
obj5[i].height = 9;
obj5[i].id = i+p1+p2+p3+p4;
obj5[i].catalog = 5;
obj5[i].init();
objects.push_back(&obj5[i]);
}
int itemsTotal = p1+p2+p3+p4+p5;
int itemsAvailable = itemsTotal;
// start the stacking process
// we just use random method
srand(time(NULL));
while(itemsAvailable != 0) {
int selected=rand()%itemsAvailable;
int index = -1;
int i;
for(i=0; i <itemsTotal; i++)
{
if(!objects[i]-> stacked) {
index++;
if(index==selected) break;
}
}
short aWay = rand()%6; // 6 ways totally
objects[i]-> reShape(aWay);
if(!box.stackObject(objects[i]))
{
// reset everything
box.reset();
itemsAvailable = itemsTotal;
for(i=0; i <itemsTotal; i++)
objects[i]-> init();
}
else {
objects[i]-> stacked = true;
itemsAvailable--;
}
}
cout < < "Successful! " < < endl;
box.print();
return 0;
}
