问题解决问题：带两个变量和不同总数的背包变量

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

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<；的此函数值后我<；=N、 0<；=j<；=和（E[]）和0<；=k<；=W+和（W[]），求所有0<；=j<；=和（E[]）和0<；=k<；=W+和（W[]），使得f（N，j，k）<；=B

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

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

无约束费用的贪心算法

以下简单的O（N*logn）-时间，O（N）-空间算法可在没有成本约束的情况下最大化行驶距离。我认为这很有趣，因为它证明了正确性

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

证明这一正确的一个关键因素是观察到，每当我们组合两组多组电池（我们可以认为汽车是一个总是选择的能量水平为0的电池）时，所得到的多组的平均值严格地在原来的两种方法之间。我称之为“平均介数”引理；参见引理1here以获得证明。直观地说，这意味着（呵呵）无论何时，只要我们可以添加一个能量密度比目前选择的多组电池更高的电池，我们都应该这样做，因为这两个多组电池（新电池是大小为1的多组电池）的组合结果将严格介于两者之间，因此严格高于目前选择的多组电池

运行上述算法将选择多组电池，其中将选择排序列表中的一些初始数量的电池，而不会选择其他电池。通过平均介数引理，该算法在具有这种形式的所有解中（即，在仅选择列表中某些初始电池数的解中）明确地选择最优多解集。为了确定它总体上选择了一个最优的解决方案，我们需要证明，没有一个解决方案是“跳过”列表中的一个或多个电池，然后再选择一个或多个更低的电池会更好

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

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

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