python - 解题题：具有两个变量和不同总和的背包变化

Question

我试图找出这个问题的解决方案，这与背包问题非常相似，但我不确定我应该拥有哪些状态或如何记住它们。

你有一辆重量为 W 单位的电动汽车，你想让它尽可能长地行驶。要做到这一点，你必须从 N 电池中挑选，它们也有能量 e、重量 b 和成本 c。您的汽车可以行驶的时间是 t = Etotal / Wtotal（您选择的电池能量之和除以您选择的电池重量之和 + 汽车本身的重量）假设您有预算B，你的车最多可以行驶多长时间？

例子：

INPUT:
N = 10 /number of batteries to choose
B = 1000 /budget
W = 20 /weight of car
#N batteries with numbers e (energy), w (weight), c (cost)
40 40 40
1 1 1
70 30 60
100 20 700
80 50 200
30 1 200
100 100 1
20 1 500
30 20 100
70 50 100

OUTPUT:
3.17073170731707

标签： pythonalgorithmdynamic-programming

Answer 1

简单的 DP 算法

我们可以通过选择前 i 个电池的某个子集来计算能够准确实现总能量 j 和总重量 k 的解决方案的最小成本 f(i, j, k)。这是由以下给出的：

f(0, 0, W) = 0
f(0, j!=0, W) = INF
f(0, j, k!=W) = INF
f(i>0, j, k<W) = INF
f(i>0, j, k>=W) = min(f(i-1, j, k), f(i-1, j-E[i], k-W[i]) + C[i])

其中 E[i]、W[i] 和 C[i] 分别是电池 i 的能量、重量和成本。在对所有 0 <= i <= N、0 <= j <= Sum(E[]) 和 0 <= k <= W+Sum(W[]) 计算此函数的值后，求 j/ 的最大值/ k 超过所有 0 <= j <= Sum(E[]) 和 0 <= k <= W+Sum(W[]) 使得 f(N, j, k) <= B。

使用 3D DP 表的直接实现将花费时间和空间 O(N*Sum(E[])*(W+Sum(W[]))) 时间和空间。但是由于递归永远不需要在第一个参数 i 中返回超过 1 步，我们可以使最外层循环增加 i 并从 DP 表中删除第一个维度，同时覆盖它的条目，以降低空间复杂度N的一个因素。

上面的 DP 计算最小成本，但它可以“旋转”以优化三个变量中的任何一个（给定能量和重量的最小成本、给定成本和重量的最大能量，或给定能量和成本的最小重量）。最有效的方法是优化具有最大范围的变量，因为时间和空间复杂度涉及其余两个变量的范围的乘积。

无约束成本的贪心算法

如果没有成本限制，以下简单的 O(N*log N) 时间、O(N) 空间算法可最大化行进距离。我认为这很有趣，因为正确性的证明。

1. 按能量除以重量的降序对电池进行排序（您可以将其视为“能量密度”）。
2. 继续从此列表中添加电池，直到下一个电池的能量/重量小于迄今为止选择的电池（和汽车）的（总能量）/（总重量）。

证明这个正确性的一个关键因素是观察到，每当我们组合两个多组电池时（我们可以认为汽车是能量级别为 0 的始终选择的电池），所得多组的平均值严格在原始电池组之间两种手段。我称之为“平均介数”引理；请参阅此处的引理 1以获得证明。直观地说，这意味着（呵呵）每当我们可以添加比目前选择的多组电池具有更高能量密度的电池时，我们应该——因为组合这两个多组的结果（新电池是大小为 1 的多组）将严格介于它们之间，因此严格高于迄今为止选择的多组电池。

运行上面的算法将选择多组电池，其中将选择排序列表中的一些初始数量 s 的电池，并且不会选择其他电池。通过平均介数引理，该算法清楚地在具有这种形式的所有解决方案中（即，在仅选择列表中某些初始电池数量的解决方案中）选择最优的多组解决方案。为了确定它选择了一个整体的最佳解决方案，我们需要证明没有解决方案会“跳过”这个列表中的一个或多个电池，然后选择一个或多个电池进一步向下可以更好。

相反，假设存在一个跳过电池的最优解 X，并且该解严格优于贪心算法产生的解 Y。让 i 成为 X 跳过的第一个电池。因此 X 和 Y 共享第一个 i-1 电池。有2种情况：

1. E[i]/W[i] 严格大于 X 的能量/权重。在这种情况下，通过平均介数引理，我们可以将电池 i 添加到 X 以产生严格优于 X 的解决方案，这与X 的最优性。
2. E[i]/W[i] 小于或等于 X 的能量/重量。

继续案例 2，考虑由 X 选择的电池的子多集 X'（假设它必须包含至少一个电池）。因为列表是按能量/重量递减排序的，所以这些电池每个的能量/重量最多等于电池 i 的能量/重量（即 E[i]/W[i]），所以通过平均介数引理，它们的平均能量/weight 也最多等于 E[i]/W[i]。X = (XX') ∪ X'，因此根据平均介数引理，X 的平均能量/权重严格介于 (XX') 和 X' 之间。由于 X' 的平均能量/重量小于或等于 X 整体的平均能量/重量，去除从 X 到离开 (XX') 的 X' 中的电池在最好的情况下（当 X 和 X' 的平均值相等时）将保持平均值不变，否则会增加平均值。无论哪种方式，我们都构建了一个新的解决方案 (XX')，其平均能量/重量至少与 X 一样高，并且由列表中的第一个 i-1 电池组成 - 即，贪婪形式的解决方案算法已知最大化。