Straightforward DP algorithm
We can compute the minimum cost f(i, j, k) of a solution that achieves exactly total energy j and total weight k by choosing some subset of the first i batteries. This is given by:
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])
where E[i], W[i] and C[i] are the energy, weight and cost of battery i, respectively. After computing values of this function for all 0 <= i <= N, 0 <= j <= Sum(E[]) and 0 <= k <= W+Sum(W[]), find the maximum of j/k over all 0 <= j <= Sum(E[]) and 0 <= k <= W+Sum(W[]) such that f(N, j, k) <= B.
A direct implementation using a 3D DP table will take time and space O(N*Sum(E[])*(W+Sum(W[]))) time and space. But since the recursion never needs to reach back further than 1 step in the first parameter i, we can make the outermost loop increase i and drop the first dimension from the DP table, overwriting its entries as we go, to drop the space complexity by a factor of N.
The above DP computes minimum costs, but it could be "rotated" to optimise for any of the three variables (minimum cost for given energy and weight, maximum energy for given cost and weight, or minimum weight for given energy and cost). The most efficient approach is to optimise for the variable with the largest range, since the time and space complexity involve the product of the ranges of the remaining two variables.
Greedy algorithm for unconstrained costs
The following simple O(N*log N)-time, O(N)-space algorithm maximises the distance travelled if there are no cost constraints. I think it's interesting because of the proof of correctness.
- Sort batteries in decreasing order by energy divided by weight (you could think of this as "energy density").
- Keep adding batteries from this list until the next battery has energy/weight less than the (total energy)/(total weight) of the batteries (and car) chosen so far.
A key element in proving this correct is the observation that, whenever we combine two multisets of batteries (we can consider the car to be an always-chosen battery with energy level 0), the mean of the resulting multiset is strictly in between the original two means. I'll call this the "mean-betweenness" lemma; see Lemma 1 here for a proof. Intuitively this means (hehe) that whenever we can add a battery with higher energy density than the multiset of batteries chosen so far, we should -- since the result of combining these two multisets (the new battery is a multiset of size 1) will be strictly in between them, and thus strictly higher than the multiset of batteries chosen so far.
Running the algorithm above will choose a multiset of batteries in which some initial number s of batteries in the sorted list will be chosen, and no other batteries will be chosen. By the mean-betweenness lemma, the algorithm clearly chooses an optimal multiset of solutions among all solutions having this form (that is, among solutions that choose only some initial number of batteries in the list). To establish that it chooses an optimal solution overall, we need to show that no solution that "skips over" one or more batteries in this list and then chooses one or more batteries further down can be better.
Suppose to the contrary that there exists an optimal solution X that skips a battery, and that this solution is strictly better than the solution Y produced by the greedy algorithm. Let i be the first battery that X skips. Thus X and Y share the first i-1 batteries. There are 2 cases:
- E[i]/W[i] is strictly greater than the energy/weight of X. In this case, by the mean-betweenness lemma, we can add battery i to X to produce a solution that is strictly better than X, contradicting the optimality of X.
- E[i]/W[i] is less than or equal to the energy/weight of X.
Continuing with case 2, consider the submultiset X' of batteries chosen further down the list by X (by assumption this must contain at least one battery). Because the list is ordered by decreasing energy/weight, these batteries each have energy/weight at most equal to that of battery i (namely, E[i]/W[i]), so by the mean-betweenness lemma their mean energy/weight is also at most equal to E[i]/W[i]. X = (X-X') ∪ X', so by the mean-betweenness lemma, the mean energy/weight of X is strictly between (X-X') and X'. Since the mean energy/weight of X' is less than or equal to the mean energy/weight of X overall, removing the batteries in X' from X to leave (X-X') will in the best case (when the means of X and X' are equal) leave the mean unchanged, and otherwise increase it. Either way, we have constructed a new solution (X-X') with mean energy/weight at least as high as X and which consists of the first i-1 batteries in the list -- that is, a solution of the form that the greedy algorithm is known to maximise over.
