最近在看算法，dp 和背包相关的
想到这种实际的题目如下。
有一个 20*10 米的仓库，不考虑门进出货物的限制。
都是平面堆放。
有三种货物
1*2 米 价值 5 元
2*3 米 价值 3 元，
2*4 米 价值 4 元。
怎么堆放货物，总价值最多？
同一种货物可以重复使用。
这个是完全背包问题？
二维的都不会，扩展到 3 维仓库，比如 20*10*5 米的立体仓库，更加难了。
如果求解完，能出个 3 维图演示堆放方案，就更好了。
感觉这个还要考虑体积碰撞和堆放的旋转，比单计算体积或者重量限制，复杂度大很多。
物流公司应该用的到。
想到这种实际的题目如下。
有一个 20*10 米的仓库，不考虑门进出货物的限制。
都是平面堆放。
有三种货物
1*2 米 价值 5 元
2*3 米 价值 3 元，
2*4 米 价值 4 元。
怎么堆放货物，总价值最多？
同一种货物可以重复使用。
这个是完全背包问题？
二维的都不会，扩展到 3 维仓库，比如 20*10*5 米的立体仓库，更加难了。
如果求解完，能出个 3 维图演示堆放方案，就更好了。
感觉这个还要考虑体积碰撞和堆放的旋转，比单计算体积或者重量限制，复杂度大很多。
物流公司应该用的到。
11 条回复 • 2024-12-02 17:11:46 +08:00
 |
1
wnpllrzodiac OP 2*4 调整为 8 元，比较好，不然直接全部无脑放 1*2 就好了
|
 |
2
python35 2 天前
从单位面积的价值最大话来说 即使 2*4 调为 8 元，我还是选择全部放 1*2 的
|
|
3
wnpllrzodiac OP @python35 不行，2*4 要改到 20 ，不然被你们钻空子了
|
 |
4
xuld 2 天前
这个题目不错，价格不影响算法本身，只影响结果
转换公式为： 放完第 N 个货物的剩余可用面积 = 放完第 N - 1 个货物的剩余可用面积 + 第 N 块货物的面积 这样可以求出所有货物的放法，然后取价值最大 |
|
5
wnpllrzodiac OP @xuld 这个我也想到了，但是切割多次长方形后，变成了一个不规则的剩余图形。
|
 |
6
aeron 2 天前
整数规划问题，用求解器求解
|
 |
7
yuyang 2 天前
@wnpllrzodiac 简单，剩余的不规则图形看成 2 个长方形就是了
|
 |
8
SeaTac 2 天前 via iPhone
请 google 2d knapsack
话说回来为啥看这个 作为面试题难度也太高了点 |
 |
9
guoph 2 天前
Two-dimensional knapsack problem: https://doi.org/10.1016/S0377-2217(02)00123-6
|
|
10
xuld 2 天前
@wnpllrzodiac
无论最终怎么放，最后可能会产生一个空隙，而且这个空隙的面积小于任何一个货物。 先假想有一个货物，是 1*1 ，价值 0 ，这个货物可放在任何一个空隙 所以把这个货物放进去，那么最终货物的面积就一定能是占满整个仓库的。 这样算面积的时候，就不是不规则形状了。 所以，最终方法： 1. 将货物的价值除以面积，得到每个货物的性价比。 2. 按性价比存放货物，先满足长的要求，找到所有的可能。 3. 然后在每种情况考虑宽的要求，再求出性价比。 |
 |
11
CHENXCHEN 1 天前
经典的装箱问题，它是 NP 完全问题，目前不存在有效时间内求得精确解的算法，想要求的精确解必须要枚举所有可能性，在空间和物品数足够多的情况下，排列组合的时空复杂度会爆炸，目前业界常见常用的是启发式算法，求近似值
|
Select Language