<h2 id="straightforward-dp-algorithm">DP算法</h2>
<p>我们可以通过选择前i个电池的某个子集来计算精确获得总能量j和总重量k的解决方案的最小成本f(i,j,k)。这是由以下公式得出的:</p>
<pre><code>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])
</code></pre>
<p>其中E[i]、W[i]和C[i]分别是电池i的能量、重量和成本。计算所有0<;的此函数值后我<;=N、 0<;=j<;=和(E[])和0<;=k<;=W+和(W[]),求所有0<;=j<;=和(E[])和0<;=k<;=W+和(W[]),使得f(N,j,k)<;=B</p>
<p>使用3D DP表的直接实现需要时间和空间O(N*Sum(E[])*(W+Sum(W[]))时间和空间。但是,由于递归不需要在第一个参数i中返回超过1步,我们可以使最外层的循环增加i并从DP表中删除第一个维度,在执行时覆盖其条目,从而将空间复杂度降低N倍</p>
<p>上述DP计算最小成本,但可“旋转”以优化三个变量中的任何一个(给定能量和重量的最小成本、给定成本和重量的最大能量或给定能量和成本的最小重量)。最有效的方法是优化具有最大范围的变量,因为时间和空间复杂性涉及剩余两个变量范围的乘积</p>
无约束费用的贪心算法</h2>
<p>以下简单的O(N*logn)-时间,O(N)-空间算法可在没有成本约束的情况下最大化行驶距离。我认为这很有趣,因为它证明了正确性</p>
<ol>
<li>按能量除以重量的降序排列电池(您可以将其视为“能量密度”)</李>
<li>继续添加此列表中的电池,直到下一个电池的能量/重量小于到目前为止所选电池(和汽车)的(总能量)/(总重量)</李>
</ol>
<P>证明这一正确的一个关键因素是观察到,每当我们组合两组多组电池(我们可以认为汽车是一个总是选择的能量水平为0的电池)时,所得到的多组的平均值严格地在原来的两种方法之间。我称之为“平均介数”引理;参见引理1<a href="https://cs.stackexchange.com/a/125021/1984">here</a>以获得证明。直观地说,这意味着(呵呵)无论何时,只要我们可以添加一个能量密度比目前选择的多组电池更高的电池,我们都应该这样做,因为这两个多组电池(新电池是大小为1的多组电池)的组合结果将严格介于两者之间,因此严格高于目前选择的多组电池</p>
<p>运行上述算法将选择多组电池,其中将选择排序列表中的一些初始数量的电池,而不会选择其他电池。通过平均介数引理,该算法在具有这种形式的所有解中(即,在仅选择列表中某些初始电池数的解中)明确地选择最优多解集。为了确定它总体上选择了一个最优的解决方案,我们需要证明,没有一个解决方案是“跳过”列表中的一个或多个电池,然后再选择一个或多个更低的电池会更好</p>
<p>相反,假设存在一个跳过电池的最优解X,并且该解严格优于贪婪算法产生的解Y。让我成为X跳过的第一个电池。因此,X和Y共用第一个i-1电池。有两种情况:</p>
<ol>
<li>E[i]/W[i]严格大于X的能量/重量。在这种情况下,通过平均介数引理,我们可以将电池i添加到X中,以产生严格优于X的解决方案,这与X的最优性相矛盾</li>
<li>E[i]/W[i]小于或等于X的能量/重量</li>
</ol>
<P>继续例2,考虑从Li下选择的电池的子集合X’。st乘以X(假设该电池必须至少包含一个电池)。由于列表是按能量/重量递减排序的,因此这些电池的能量/重量最多等于电池i的能量/重量(即E[i]/W[i]),因此通过平均介数引理,它们的平均能量/重量最多也等于E[i]/W[i]。X=(X-X')∪ 因此,通过平均介数引理,X的平均能量/重量严格介于(X-X')和X'之间。由于X'的平均能量/重量小于或等于整个X的平均能量/重量,<em>将X'中的电池从X移除(X-X')在最佳情况下(当X和X'的平均值相等时)保持平均值不变,否则会增加平均值。无论哪种方式,我们都构建了一个新的解决方案(X-X'),其平均能量/重量至少高达X,并由列表中的第一个i-1电池组成,即贪婪算法已知的最大化形式的解决方案</p>