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