New answers tagged dynamic-programming
2
votes
Efficient search of a large set of documents to find documents that only contain a particular set of words
You are trying to compute the set
$$E = \{e \in D \mid e \subseteq K \land e \cap S \ne \emptyset\}.$$
There is a naive algorithm. Store $K,S$ in a hashtable (using a hash function that maps each ...
D.W.♦
- 140k
3
votes
Allocating m rooms of varying capacity to n booking requests of varying sizes
One plausible approach is to use integer linear programming. Introduce 0-or-1 variables $x_{q,r}$, where $x_{q,r}=1$ means that room $r$ is assigned to request $q$. Then you can write down linear ...
D.W.♦
- 140k
1
vote
Counting the number of parenthesization
The split in a product is between the two outermost pairs of parantheses. For example, in $((a*b)*(c*d))*(e*f)$, the split is between the $d$ and $e$ because the last multiplication that is performed ...
- 1,005
2
votes
Counting the number of parenthesization
Suppose you have $n$ matrices $M_1, M_2, …, M_n$.
The product of all matrices is $M_1\times M_2\times…\times M_n$ and since the matrix product is associative, there is no need for parentheses from a ...
- 7,127
3
votes
Accepted
Formal Proof on why Greedy isn't working on one Particular Problem
To prove that the greedy algorithm is not optimal, it suffices to give one counterexample, i.e. one problem instance $nums$ and $mult$ such that it is possible to obtain a value that is larger than ...
- 1,005
1
vote
Optimizing an arbitrary function of 10 variables
There are only 19448 combinations of $x$'s that meet the constraints. If $f$ is arbitrary, the best you can do is enumerate all 19448 combinations and see which leads to the largest value of $f$. ...
D.W.♦
- 140k
0
votes
Accepted
Time complexity analysis for dynamic programming using memoization
The time-complexity of dynamic-programming with memoization
Here is the simple principle. Suppose an algorithm
applies dynamic programming to solve a problem,
with the majority of running time spent ...
- 33k
0
votes
Optimizing an arbitrary function of 10 variables
I do not see a dynamic programming solution. I highly doubt there is one (especially, a polynomial time).
- 129
-1
votes
Factor a number in the longest possible product of distinct numbers
A nice problem. You will have to do some rather exhaustive / exhausting search :-) First, ignore the number 1. Make all your factors products of one or more primes, and add the number 1 at the end. ...
- 24.9k
1
vote
Solve modified knapsack problem using dynamic programming
Let $C \ge 1$ be the capacity of the knapsack and let $G_1, \dots,G_k$ be your groups, where each group is a non-empty collection of items, i.e., $G_i = \{ x^{(i)}_1, x^{(i)}_2, \dots \}$. Groups are ...
- 22.7k
2
votes
Accepted
Subdivide a graph into non-crossing triangles with maximum edge weight
With proper classification and memoization, an approach by dynamic programming runs in $O(n^3)$ time, where $n=|V|$. That seems efficient enough considering there are $n(n-1)/2$ edges.
Assume $n\ge 3 ...
- 33k
2
votes
Accepted
Largest number of disjoint paths of length $k$ and maximum reward in a tree
Given a vertex $v$, let $r(v)$ denote $v$'s rewards, let $C_v$ be the set of $v$'s children, and let $T_v$ denote the subtree of $T$ rooted in $v$.
Given a vertex $x$ at depth $d_T(x) \ge k$ in $T$, ...
- 22.7k
0
votes
Dynamic Programming - Difficult Jumping Frog Problem
We shall use bottom-up dynamic programming, where subproblems of smallest size are solved first, and their solutions are used to update the solutions to larger subproblems. Let $A$ be a two-...
- 1,005
0
votes
Dynamic Programming - Difficult Jumping Frog Problem
Dynamic programming is about how to implement a problem, but I think you need to solve the problem first.
A good way to solve problems in this nature is with recursion, which to solve the problem, we ...
- 59
1
vote
Why Least Cost Airline Fare problem shows optimal substructure when given a certain intermediate stops?
It is better to ignore the confusing text below, which was added to that page of Wikipedia by an anonymous user on "20 August 2020", as shown on this comparison page.
However, if the ...
- 33k
Top 50 recent answers are included