算法题 求教。是背包问题吗？感觉很复杂

[wnpllrzodiac]

最近在看算法，dp 和背包相关的

想到这种实际的题目如下。



有一个 20*10 米的仓库，不考虑门进出货物的限制。

都是平面堆放。

有三种货物

1*2 米 价值 5 元

2*3 米 价值 3 元，

2*4 米 价值 4 元。

怎么堆放货物，总价值最多？

同一种货物可以重复使用。



这个是完全背包问题？

二维的都不会，扩展到 3 维仓库，比如 20*10*5 米的立体仓库，更加难了。



如果求解完，能出个 3 维图演示堆放方案，就更好了。

感觉这个还要考虑体积碰撞和堆放的旋转，比单计算体积或者重量限制，复杂度大很多。

物流公司应该用的到。

[wnpllrzodiac]

2*4 调整为 8 元，比较好，不然直接全部无脑放 1*2 就好了

[python35]

从单位面积的价值最大话来说 即使 2*4 调为 8 元，我还是选择全部放 1*2 的

[wnpllrzodiac]

@python35 不行，2*4 要改到 20 ，不然被你们钻空子了

[xuld]

这个题目不错，价格不影响算法本身，只影响结果

转换公式为：
放完第 N 个货物的剩余可用面积 = 放完第 N - 1 个货物的剩余可用面积 + 第 N 块货物的面积

这样可以求出所有货物的放法，然后取价值最大

[wnpllrzodiac]

@xuld 这个我也想到了，但是切割多次长方形后，变成了一个不规则的剩余图形。

[aeron]

整数规划问题，用求解器求解

[yuyang]

@wnpllrzodiac 简单，剩余的不规则图形看成 2 个长方形就是了

[SeaTac]

请 google 2d knapsack
话说回来为啥看这个 作为面试题难度也太高了点

[guoph]

Two-dimensional knapsack problem: https://doi.org/10.1016/S0377-2217(02)00123-6

[xuld]

@wnpllrzodiac
无论最终怎么放，最后可能会产生一个空隙，而且这个空隙的面积小于任何一个货物。
先假想有一个货物，是 1*1 ，价值 0 ，这个货物可放在任何一个空隙
所以把这个货物放进去，那么最终货物的面积就一定能是占满整个仓库的。

这样算面积的时候，就不是不规则形状了。

所以，最终方法：
1. 将货物的价值除以面积，得到每个货物的性价比。
2. 按性价比存放货物，先满足长的要求，找到所有的可能。
3. 然后在每种情况考虑宽的要求，再求出性价比。

[CHENXCHEN]

经典的装箱问题，它是 NP 完全问题，目前不存在有效时间内求得精确解的算法，想要求的精确解必须要枚举所有可能性，在空间和物品数足够多的情况下，排列组合的时空复杂度会爆炸，目前业界常见常用的是启发式算法，求近似值