我正在试图找出这个问题的解决方案，它与背包问题非常相似，但我不确定我应该有什么状态，也不知道如何记住它们。
你有一辆重量为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
直接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<=求和(E[])和0<=k<=W+Sum(W[])，在所有0<=j<=求和(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)-空间算法最大化行驶距离。我认为这很有趣，因为它证明了正确性。
- 按能量除以重量的递减顺序对电池进行排序(你可以把它看作"能量密度")
- 继续从该列表中添加电池，直到下一个电池的能量/重量小于迄今为止选择的电池(和汽车)的(总能量)/(总重量)
证明这一正确性的一个关键因素是观察到，每当我们组合两组多组电池时(我们可以认为汽车是能量水平为0的始终选择的电池)，所得到的多组电池的平均值严格介于原始的两个平均值之间。我称之为"强者"；平均介数"；引理；参见这里的引理1。直观地说，这意味着(呵呵)每当我们可以添加一个能量密度比迄今为止选择的多组电池更高的电池时，我们都应该——因为将这两个多组电池(新电池是一个尺寸为1的多组)组合在一起的结果将严格地介于它们之间，因此严格地高于目前选择的多集电池。
运行上面的算法将选择多组电池，其中排序列表中的一些初始电池数s将被选择，而不会选择其他电池。通过平均介数引理，该算法在所有具有这种形式的解中(即，在只选择列表中某个初始电池数的解中)清楚地选择了一个最优的多解集。为了确定它总体上选择了最优解，我们需要证明；跳过"；在该列表中的一个或多个电池，然后选择一个或更多个更靠下的电池可能会更好。
相反，假设存在跳过电池的最优解X，并且该解严格优于贪婪算法产生的解Y。让我成为X跳过的第一个电池。因此，X和Y共享第一i-1电池。有两种情况：
- E[i]/W[i]严格大于X的能量/重量。在这种情况下，通过平均介数引理，我们可以将电池组i加到X上，以产生严格优于X的解，这与X的最优性相矛盾
- E[i]/W[i]小于或等于X的能量/重量
继续情况2，考虑列表后面X所选电池的子集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，并且由列表中的第一个i-1电池组成——也就是说，贪婪算法已知最大化的形式的解决方案。