New answers tagged dynamic-programming
1
The second implementation is correct (so Theorem 2.2 survives): If the condition $c(v) > c(u)$ causes the inner while to halt, that same value of $v$ will be give the optimal value for every following value of $g$, simply because the condition is independent of $g$.
0
A possible solution may be to compute the all pair shortest path matrix and then select the largest value in the matrix.
As long as |E|<<|V|^2 or the graph is not dense, your complexity constraint should be satisifed.
Johnson's algorithm does it in O(|V|^2 log |V|+|V||E|).
Refer to this for a better understanding of time complexity in case of ...
1
We first sort all edges according to their costs from small to large. Say the sorted edges are $e_1,e_2,\ldots,e_{n(n-1)}$, and the corresponding costs are $w_1\le w_2\le\cdots\le w_{n(n-1)}$. Then we find the minimal $i$ such that the graph is strongly connected only with the edges $e_1,\ldots,e_i$. Now $w_i$ is the minimal tank capacity we want.
Sorting ...
1
Assume you already computed the dynamic programming table DP[SIZE][LENGTH] where DP[s][l] stands for maximum profit that can be obtained by using cuts up to size s on a rod of length l. You want to find all decomposition to get the value DP[SIZE][LENGTH], to do this notice that at every step DP[s][l] we have two options, use the cut of size s or don't use it ...
1
This problem can be solved using double knapsack algorithm, just don't restrict yourself to the case $W_{i \in {1, 2}} \le \frac{W}{3}$. Find all ways to decompose elements in subsets of value $A$ and $B$. Define $C = W - A - B$ (the value of the remaining set) and let the value of such decomposition be $max(A, B, C) - min(A, B, C)$. You just need to find ...
0
The main idea is as in the answer by @izanbf1803.
However, there is a detail: after you find the minimum value m, you should go through the array again, keeping in mind that m, m - 1 and m - 2 could all be your final target. After getting the total number of steps for all three of them, just return the smallest one.
For example, if the array is [0, 0, 0], ...
4
This is only a sketch of solution (there might be some off-by-ones)
Looking at a permutation of $\{1\ldots,n\}$ is equivalent at looking its inversion table $(a_1, \ldots, a_n)$ where $a_i$ is the number of elements to the left of $i$ that are greater than $i$. Basically that gives you a bijection between $S_n$ and $\prod_{1\le i\le n} \{0,\ldots,i-1\}$ and ...
1
You could look at the answers to this question on SO: https://stackoverflow.com/questions/19372991/number-of-n-element-permutations-with-exactly-k-inversions
(in particular the part about Mahonian numbers)
Additionally, it seems that dynamic programming with memoisation runs in $\mathcal{O}(N\cdot k)$ [NB: I didn't actually check this, it's in one of the ...
1
Problem 1: Divide $𝑛$ gifts among three people so as to minimize the difference in the total cost of gifts between the most lucky and the most unlucky people.
Problem 2: Partition problem
Problem 2 is known to be NP-complete. Given an instance $A$ of problem 2, we can transform it into an instance $B$ of problem 1. Here is the rule of transformation: $A= ...
1
Say your best answer so far has a difference D, and you can give w/3 - a to the first person. The best result you can have is w/3 + a/2 to the other two, giving a difference of 3a/2, so you only proceed if 3a < 2D (actually, you will distinguish cases depending on w modulo 3 if all sizes are integers).
Then you pick items for the second person. If you ...
-1
What if having empty basket for each person, keep tracking on sum of items in each basket. So we always know which basket has the minimum value. Then we can go over list of items and put the new one, in the basket with minimum total value. The complexity of this hypothesis is $O(n \log(n))$.
Top 50 recent answers are included
