4
Let $g(i,j)$ be the gas consumed when travelling to destination $i$ with car $j$.
Guess the optimal order $\langle c_1, c_2, c_3 \rangle$ of cars (there are only $3! = 6$ possible permutations).
Define $OPT[i,j]$ as the minimum amount of gas needed for reaching the first $i$ destinations using cars $c_1, \dots, c_j$ in this order, with the constraint that ...
4
The optimization function is designed in a way to find a solution that:
uses a small number of lines
is balanced (the number of extra spaces at the end of each line should be about the same length)
Lets look first at the linear optimization function, i.e. the sum of all extra spaces.
It is very clear, that the optimal solution under that function is one ...
3
Memoization is the technique to "remember" the result of a computation, and reuse it the next time instead of recomputing it, to save time. It does not care about the properties of the computations.
Dynamic programming is the research of finding an optimized plan to a problem through finding the best substructure of the problem for reusing the computation ...
3
Dynamic programming is an algorithmic technique, algorithms are classified as dynamic programming according to what their high-level structure "looks like", not according to a formal definition. If you really wanted to, you could force some sorting algorithms to fit into the dynamic-programming paradigm.
Let $A[1:n]$ be the array to sort, assume for ...
3
I think there is some confusion in terminology here. Part of the problem is what we mean by problem and what we mean by an algorithm. But there is more to it:
Textbooks like CLRS introduce the notion of optimal substructure as a property of problems (and not algorithms directly). That's because an algorithm often transforms a problem statement into other ...
3
Here is a systematic way to approach it. I suggest you define three values:
$A_0(n)$ is the number of ways to tile a $3 \times n$ region.
$A_1(n)$ is the number of ways to tile a $3 \times n$ region with the upper-left cell already covered.
$A_2(n)$ is the number of ways to tile a $3 \times n$ region with the upper-left cell and the cell to the right of ...
2
Let $N(t,S)$ be the least number of values from $S$ which sum to $t$. The basic recurrence is
$$
N(t, S \cup \{s\}) = \min(N(t,S),N(t-s,S)+1).
$$
I'll let you work out the details.
This recurrence leads to an efficient algorithm only if we are allowed to run in time polynomial in $t$.
If we think of $t$ encoded in binary, then this algorithm runs in ...
1
One simple algorithm is as follows. Start by choosing the dumbbell which is going to have the minimum weight (we are going to try all possibilities). Then take the $M$ dumbbells with maximal rep among those with weight above the minimum weight (if there are enough).
To implement this algorithm efficiently, start by sorting the dumbbells according to weight ...
1
In general, you would change the question slightly: "How many ways are there to tile an X by N area by adding tiles individually and always adding the next tile so that it covers the topmost of the leftmost uncovered squares". Obviously that doesn't change the number of possible tilings at all since each square must eventually be covered.
Since you are ...
1
Suppose the gap between any two words in the same line spans a length of $k$, instead of 1. The only change needed in the Python code would be to change the line in def cost(i, j) from
w = offsets[j] - offsets[i] + j - i - 1
to
w = offsets[j] - offsets[i] + k * (j - i - 1)
def cost(i, j) returns the minimum cost needed for placing the first $j$ words, if ...
1
What about the array $[1, 3, 5]$? The supersequence $[0,1,0,3,0,5]$ is oscillating while the original sequence isn’t. In fact you can make an oscillating supersequence of any array by inserting $\min(arr)-1$ before every element of the original array.
1
In CC you can use same coin INFINITE times. But in KP you can use the same weight, not more than once. Check http://www.ccs.neu.edu/home/jaa/CSG713.04F/Information/Handouts/dyn_prog.pdf
To consider all the subsets of items, there can be two cases for every item:
(1) the item is included in the optimal subset
(2) not included in the optimal set.
...
1
Let $M=\max_i|A_i|$.
Besides the linear programming method proposed in this post (which is suitable for small $N$ and large $M,H$), you can optimize your dynamic programming method by building a larger table to reduce the time for querying the minimum value among $f(i-1,j-H),\ldots,f(i-1,j+H)$.
Let $f(i,j,k)$ be the minimum moves to stabilize the first $i$...
Only top voted, non community-wiki answers of a minimum length are eligible
