algorithm - 选择产品以获得最大的购物车值(value)

Question

鉴于商店中可用的产品列表，我需要选择一组产品到我的购物车，这样我的购物车值(value)应该是最大的。 限制就像，购物车有一个维度 l*w*h。所选产品应单独且完全适合购物车，从而为购物车提供最大可能的值(value)。每个产品可选择 1 项。

我有产品编号、价格、l、w、ht ，每个产品的重量跟我一起。这怎么能实现？？？

我想出了如下逻辑。

1. 计算购物车的体积
2. 使用价格计算每立方厘米的产品体积和产品值(value)
3. 根据值(value)/cucm 对产品列表进行排序
4. 开始从第 1、2、3 等排序列表中添加产品，直到购物车装满。
5. 如果产品无法放入购物车，请跳过它并从排序列表中选择下一个可能的产品。
6. 获得列表后，检查所选列表中的任何产品是否可以替换为体积较小但购物车值(value)更高的另一种产品。

但这并没有让我获得具有最大购物车值(value)的正确产品列表。以上逻辑有什么问题？

Answer 1

三个维度的整数值是否具有某些有限界限？那么就可以用动态规划来解决了。但我认为应该做出一些假设，例如子问题的划分应该是端到端的切割平面等。没有那个动态规划是不可行的。

这里的关键技巧是您需要考虑盒子可以多种方式定向的可能性，它是沿着购物车的三个轴对齐其自身三个维度的方式的数量。是3! = 6 对于三个维度。因此在处理第 i 个产品时的动态规划中，包括将其 3 个维度解释为 L、W、H 的所有 6 种方式。