algorithm - 根据价格和重量限制最大限度地降低运输成本

Question

当您有许多可以组合到同一个包裹中的商品(每件商品都有重量和价格)时，我正在尝试确定最低运费。约束条件如下:

1. 组合套餐的最高价格有限制(例如 15 美元)
2. 套餐费用使用下表确定:
   1. 如果包裹总重量 < 30 克，费用为 7.5 美元
   2. 如果包裹总重量 >= 30 克且 <80 克，费用为 7.5 美元 +(重量 - 30)x0.075
   3. 如果包裹总重量 >= 80 克，费用为 7.5 美元 +(重量 - 30)x0.055

只要这些商品保持在总价阈值以下，它们可以组合成的包裹数量没有限制。

我看了背包问题，但是背包问题和我的问题有两个主要区别:

1. 一个是我们不是要最大化组合项目的重量或价格，而是要最小化只能在组合后才能确定的计算变量。
2. 此外，重量和运费之间没有直接关联。

Answer 1

如果你有少量元素，可以使用二进制掩码通过暴力破解。定义 n作为项目的数量。当值m ( 0 <= m < 2^n ) 表示长度等于 n 的二进制掩码(如果需要，带前导零)。掩码显示已处理的项目(如果 i 项目已处理，掩码中的 1 位为 i)。定义 F[m]来自掩码的子项的最小成本 m .当F[m] = min(F[m xor x] + cost(x))对于所有值 x为此 m and x = x (x 是 m 的子集)。 xor和 and是二元运算。 cost(x)是一个包含面具元素的包裹 x (以下 2. from 语句)。该算法的复杂度将为 O(4^n) (对于 n <= ~14，在一台好的计算机上不到一秒钟)。但是你可以用这个 https://cp-algorithms.com/algebra/all-submasks.html并获得复杂性 O(3^n) (n <= ~18 的好工作)。首字母F[0] = 0答案是F[2^n - 1] .