集装箱装箱问题的算法? 有信心者来挑战挑战 ( 积分: 88 )

  • 主题发起人 主题发起人 sunzhanhui
  • 开始时间 开始时间
S

sunzhanhui

Unregistered / Unconfirmed
GUEST, unregistred user!
已知一个集装箱的长宽高,有无数个个尺寸各不相同的长方体的货物箱,且每个的长宽高都已知.问(1)怎样装的箱子个数最多,(2)怎样装的货物的总体积最大?
(3)简单化一点,假设货物箱的尺寸大小只有一种,怎么解决(1)(2)的问题
哪位大虾有好的算法,大家讨论讨论.
 
已知一个集装箱的长宽高,有无数个个尺寸各不相同的长方体的货物箱,且每个的长宽高都已知.问(1)怎样装的箱子个数最多,(2)怎样装的货物的总体积最大?
(3)简单化一点,假设货物箱的尺寸大小只有一种,怎么解决(1)(2)的问题
哪位大虾有好的算法,大家讨论讨论.
 
遍历问题,很麻烦啊
 
这是运筹学中的难题啊
还有一个是　画玻璃的问题　
 
同样有这方面的需求,但现在还在找寻解决方案;有时间交流一下
 
谁有好的算法,拿出来大家交流交流.互相学习嘛.
 
我们先考虑简单的吧,假设只有一种型号的货物箱,其他条件不变,该怎么处理呢?
 
可以先从平面的开始讨论 个人觉得采用动态规划的方式可以解决 高中信息学竞赛的例题
 
buttercookie 老兄,能说的具体些吗?
 
可以从一维的开始讨论.我仔细想了下,二维的蛮麻烦的(好像不能用动态规划,也可能我水平不够,三维的就更复杂了;)) 先把问题转为一维吧
转化后问题:
有一个停车带 长度为N(整数) 现有各种长度的车辆 问如何停可以使停放的车辆最多 如何停使停放的长度最长?
问题一解答:使用贪心算法,总是挑选长度最短的车辆.
推广到二维,可以选择面积最小的那个,三维就是体积最小的那个,可以得到最优近似解,但不能保证最有解,可以通过修改选择方案增加准确率.
问题二解答:一般使用回溯法遍历所有可能就能得到最优解(问题一也可以使用遍历获得精确解),但时间复杂度较高.使用动态规划可以高效的求解,动态规划请参考http://iprai.hust.edu.cn/icl2002/algorithm/algorithm/technique/dynamic_programming/
推广到二维的话使用遍历仍然可以得到最优解,但时间复杂度更高,使用减枝方案在过程中删掉明显不可能的解.使用贪心法可以得到近似最有解,即每一次都挑选尽可能大的箱子.但似乎不能使用动态规划,因为放入箱子的位置会影响答案,而在一维的状况下不会发生这种状况.
总之,原题在小规模的状况下可以使用遍历法,并配合减枝,可以得到精确解.大规模的情况下,使用贪心法并优化贪心的选择方案,可以的到近似解.
能力所限,只有这样了
 
這屬于經典問題﹐查一下資料吧﹐空想沒用的。可能得到的都不 是正解。查一下數學模型。
 
对于一维的停车问题，长度为整数的时候，是可以动态规划的，以每辆车来划分阶段。以一个一维数组length作为状态。length[n]=1表示长度为n的停放方法可以实现。那么对于长度为car的第i辆车，length[j]是否可以实现取决于length[j-car]是否为1，j从1遍历到MAXINT。最后找出最大的可以实现的length是多少就可以了。
这种方法应该也可以推广到二维。不过就是麻烦了许多。对于不是整数，而是浮点数的，就不好办了。
 
对于浮点数,我们只要保留小数点后一到两位数字,然后放大10,或100倍,变成整数来处理即可.我觉得先考虑平面的比较现实,那我们就从平面开始.就以停车场为例吧,描述如下:
已知一停车场的长宽为L,W.车也只有一种,长宽为L1,W1.
问如何摆放下最多的车辆数?
如果有了这个二维的基础.我想考虑三维的就会简单一点.
大家再接再厉!!!
 
别沉下去了，帮顶啊！！！
 
这个问题很有意思，但是解决起来颇费时间；
首先，要考虑排列时可能出现的各种情况，针对每种情况设置一个解决方案；
然后，调用这些过程就可以了！
另外， 你的问题本身就有不太明确，改为：
已知 n 个尺寸各不相同的长方体的货物箱和集装箱的长宽高,且每个货物箱的长宽高都已知.问(1)怎样装的使用的集装箱数最少?
(2)怎样装的货物的总体积最大?(这是个白痴问题)
(3)简单化一点,假设货物箱的尺寸大小只有一种,怎么解决(1)(2)的问题
这样才具有实用价值，否则解决与否又有区别？
 
这个的核心应该是背包问题吧,只是普通的背包问题着眼于重量,而不是空间,但是可以借助这个思想来处理了!
 
DP(动态规划)
f(i)=min{f(i-1)+v,f(i-1)};
O(2^N)算法
算法的思想是第I个箱子要么装要么不装
 
您必须登录或注册才可回复。

Similar threads

快
100分继续挑战算法高手（50分求购算法的续集）up有分 (100分)
回复
13
查看
519
快刀不快
快
W
装箱问题，200分求解 (200分)
2
回复
31
查看
594
wlmmlw
W
X
挑战高手－－－－足彩与算法！！！！！！！(288分)
2
回复
27
查看
597
skywolf888
S
T
设计一个集装箱货物托运单的类(200分)
回复
7
查看
488
tafeng
T
Q
急寻自定义控件的保存和恢复技术（有挑战性）(100分)
回复
11
查看
174
slb_anders
S
后退
顶部