New answers tagged

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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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$. ...
user avatar
  • 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 ...
user avatar
  • 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).
user avatar
  • 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. ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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$, ...
user avatar
  • 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-...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 33k

Top 50 recent answers are included