Questions tagged [dynamic-programming]
Questions about problems that can be solved by combining recursively obtained solutions of subproblems.
571
questions
-2
votes
0answers
11 views
Do branch - bound and dynamic programming give same solutions for a tsp problem interms of path and cost? , also same number of solutions?
Do branch - bound and dynamic programming give same solutions for a tsp problem interms of path and cost? , also same number of solutions?
2
votes
1answer
39 views
Find $n'th$ perfect number , where perfect number is a positive integer whose sum of digits is $10$
For example $46$ is a perfect number , since $4+6=10$ . If $n=1$ , answer is $19$. If $n=2$ , answer is $28$. If $n=3$ , answer is $37$ and so on .We need to make a program which takes $n$ and ...
1
vote
0answers
34 views
Weighted Activity Selection Problem with allowing shifting starting time
I have some activities with weights, and I would like to select non overlapping activities by maximizing the total weight. This is known problem and solution exists.
In my case, I am allowed to ...
1
vote
0answers
12 views
Dancing Links use in tiling problems
I'm using Knuth's Dancing Links (dlx) algorithm to solve for solutions to tiling a 2xN rectangle using 3 different pieces of one, two, or three squares. It's working correctly in its basic form but ...
0
votes
0answers
26 views
Minimum changes to obtain an alternating sequence [duplicate]
I've been studying dynamic programming lately and came across a problem that is, I believe (might be wrong, though), a modification of the classic longest alternating subsequence (LAS) problem.
But ...
-1
votes
1answer
34 views
You have K amoebas and one amoeba can divide into A,B,C amoebas after one instruction then find the minimum no. of instruction to have N amoebas
. You have developed an artificial amoeba, and you can control exactly how it divides.
Each individual amoeba can be instructed to divide into A, B, or C amoebas. That
is, if you instruct an amoeba to ...
0
votes
1answer
17 views
Determining whether a change in an memoized algorithm will improve the performance
I have an algorithm that constructs an optimal binary tree using dynamic programming. After introducing what I thought would be an optimization, the algorithm became over 2 times slover. Question: Is ...
0
votes
0answers
19 views
Dynamic programming algorithm with an O(n) performance that will give the optimal solution
I am currently learning the dynamic substructure and optimal solution for the coin change-making, and one of the questions given from my teacher is to describe an overall O(n) dynamic programming ...
2
votes
0answers
35 views
Finding a non negative combination of integers that adds up to a certain number [duplicate]
I have a set of positive numbers: ${n_1,n_2,...n_k}$ s.t. $n_1>n_2>\dots >n_k$.
I want to find an array of non-negative integers $c_1,c_2,\dots,c_k$ such that
$$n_1c_1 + n_2c_2 + \dots + ...
2
votes
1answer
37 views
Queries on knapsack
Given items with weights $w_{1}, w_{2}, \dots, w_{n}$ and queries of form $(l, r, w)$ asking for possibility to find a subset of items $w_{l}, w_{l + 1}, \dots, w_{r}$ with total weight $w$, how to ...
0
votes
0answers
55 views
Minimum increment/decrement to change an array into non-decreasing sequence
I was trying to solve a codeforces problem https://codeforces.com/contest/713/problem/C.
Basically we have to convert a sequence in minimum increment decrement operations to a strictly increasing ...
1
vote
1answer
24 views
How to solve Assigment problem on SPOJ? [closed]
Problem Link - Assign .This problem is known as assignment problem.
I read few solutions Here is one and they are trying to solve it using Bit-masking and DP .I tried and thought hard to ...
2
votes
1answer
50 views
Multiple choice knapsack dynamic programming
Giving a the following:
A list of a store items $T=\{t_1, t_2,...,t_n\}$.
A list of prices of each item $P=\{p_1, p_2,...,p_n\}$.
A list of quantities of each item $Q=\{q_1, q_2,...,q_n\}$...
1
vote
1answer
46 views
Converting a greedy algorithm to a dynamic programming algorithm
Suppose I have a greedy approach to solve a certain problem. Say, I wish to solve the problem of coloring a particular graph. Now, my naive approach would be:
First, find a maximum indpendent set of ...
-1
votes
1answer
57 views
How to compute total number of subsequences of length k from a word of length N?
A subsequence of a word is obtained by dropping some letters from it. The letters
that are dropped need not be consecutive. For instance, ba, bna and banaa are all
subsequences of the word banana.
We ...
0
votes
0answers
21 views
Dynamic programming solution to Matrix chain multplication order - time complexity
I am unable to understand why the dynamic programming solution to Matrix chain multiplication order problem is O(n^3). Can someone please help understand the reasoning?
To me, it looks like the ...
2
votes
2answers
32 views
Minimum words in a string given a dictionary
The question is: Given a dictionary consisting of a set of words and a string: find the minimum number of words the string can be split into. If the string can not be decomposed into a list of words ...
1
vote
1answer
25 views
Grokking pseudo-code for solution to gas station problem
I'm trying to grok the pseudo-code for the gas station problem (which I think we should start calling the charging station problem but that's a different story) given as Fill-Row in Fig. 1 in To Fill ...
3
votes
0answers
42 views
Forbidden Sequence Dynamic Programming
Given a finite set $\Omega$, I have the following problem. Say there is a list of forbidden subsequences $F \subset \Omega \cup \Omega^2 \cup \Omega^3 \dots \Omega^\infty$, while we do not know the ...
1
vote
0answers
36 views
How does the asterisk (*) work in the wildcard matching problem?
This is a wildcard matching problem. Given a pattern P containing letters and character * that can match an arbitrary string of characters (including an empty string), my task is to write a polynomial-...
1
vote
2answers
43 views
Find the minimal tank capacity to be able to travel from any city to any other
There are $n$ cities in the country. The car can go from any city $u$ to city $v$, On this road it spends $w_{u,v} > 0$ fuel. At the same $w_{u,v}$ can differ from $w_{v, u}$. The task is to find ...
2
votes
0answers
19 views
Seeking an algorithm for finding the partition of data on an interval that maximizes the minimum fitness among the blocks
In the paper "An algorithm for optimal partitioning of data on an interval" (link) the authors describe an algorithm for partitioning data on an interval to maximize a fitness function. The fitness ...
0
votes
0answers
56 views
How to solve this dynamic programming puzzle on matrix?
We are given 4 integers N,M ,Q and Z.
Initially,the matrix has all zeroes in it.
We have to perform Q operations on the matrix.
In each operation, any cell of the matrix can be selected(same cell ...
0
votes
2answers
93 views
number of permutation with k inversions
We are given two numbers N and K.
N <= 10^9.
K<=min{1000,(N*(N-1))/2}
We need to find numbers of permutations of ( 1 to N ) such that inversions are exactly K.
If N was <= 10^3. It would ...
3
votes
4answers
93 views
Divide $n$ 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
Divide $n$ gifts of different values among three people so as to minimize the difference in the total cost of the gifts for the most lucky and the most unlucky persons.
The total value of $n$ gifts ...
1
vote
1answer
56 views
Dynamic programming and multiple optimal solutions
I have tried researching how I can handle multiple optimal solutions based using dynamic programming. The answer is found from this question is simply that you have to backtrack. What if this is not ...
2
votes
1answer
80 views
Algorithm to find longest path in a tree that is smaller than x
Suppose we have a weighted binary tree $G$ where the nodes are towns and edges are streets with edge weights being the travel time and we want to find out whether it is possible to travel from any ...
3
votes
1answer
70 views
DP for Weighted Interval Scheduling: why is sorting by finish time necessary?
Problem In the weighted interval scheduling problem, we want to find the maximum-weight subset of nonoverlapping jobs, given a set $J$ of jobs that have weights associated with them. Job $i \in J$ has ...
3
votes
2answers
47 views
Compute highest-scoring segmentation
I have the following problem:
There is a "clean" sequence of sequences, say:
clean = [
[1, 2],
[3],
[4, 5]
]
And a "noisy" sequence which is not ...
2
votes
0answers
33 views
Dynamic Program for this Weighted Possion-Binomial Problem?
Setup: Suppose we have $n$ independent Bernoulli random variables, say $\boldsymbol{X} = \{X_1, ..., X_n\}$ each with prior $\mathbb{P}(X_j = 1) = p_j$, and weights between $-1$ and $1$, say $W = \{...
1
vote
1answer
35 views
Ford Fulkerson maximum flow for all vertices
Suppose we have a graph $G(E,V)$ with a source node $s$. Now for any $t\in V \setminus s$ I can find the maximum flow from $s$ to all possible $t$ by using the Ford Fulkerson algorithm $|V|-1$ times, ...
0
votes
0answers
23 views
Can anyone provide proof of second equation of rod cutting problem in CLRS section 15.1
While going through ROD CUTTING problem of DP from CLRS, I noticed the optimal structure of the rod cutting problem is :
𝑟𝑗=max{𝑝𝑛,𝑟1+𝑟𝑘−1,𝑟2+𝑟𝑗−2,...,𝑟𝑗−1+𝑟1}
In overhead approach, ...
0
votes
0answers
46 views
Counting number of apples in an apple tree with given number of layers
This problem comes from a competitive programming question, and it seems to require dynamic programming.
There are several layers of apples arranged in a formation with each apple having a value ...
2
votes
1answer
78 views
Gas Station problem : Fixed path variation
Given a set of cities where you need a certain amount of fuel to travel from one city to another, each city has a different fuel price and you can only load K amount of fuel to the vehicle. The path ...
2
votes
0answers
25 views
Selecting objects to maximize value while under multiple constraints
I think it will be best to explain the problem first and then explain what I am thinking:
I have a dataset similar to the following:
...
1
vote
0answers
60 views
How to approach backtracking when using immutable types (Python)? [closed]
In Python when we are building a recursive algorithm that uses backtracking a mutable type such as a list is great to use. It can be modified at each call in our recursion tree, then returned back to ...
2
votes
2answers
82 views
How can I solve this problem using dynamic programming?
I'm stuck in this problem and I would need some help:
Given an array arr, in each step, 1, 2 or 5 units have to be incremented to all but one item of the array. ...
2
votes
2answers
103 views
How can we find a palindrome within a string?
The problem requires us to find the substring within a string which happens to be a palindrome. Multiple palindromes are also allowed.
For example, in "LODHIHDAK" "DHIHD" is a palindrome.
Comparing ...
1
vote
1answer
41 views
Winning strategy using Dynamic Programing
Let $G=(V,E)$ be a DAG and let $v_0\in V$.
Alice and Bob are playing a game in which every player has his own turn and Bob is starting. In every turn $i$, the player is picking an edge $e=(v_i,x)$, ...
0
votes
1answer
64 views
Count the number of ways numbers 1,2,…,n can be divided into two sets of equal sum
count the number of ways numbers 1,2,…,n can be divided into two sets of equal sum.
This is my recursive algorithm, what is wrong here?:
...
1
vote
1answer
81 views
Given price and number of pages of each book, What is the maximum number of pages you can buy?
You are in a book shop which sells n different books. You know the price and number of pages of each book.
You have decided that the total price of your purchases will be at most x. What is the ...
1
vote
1answer
125 views
How to find Maximum perimeter of rectangle in a grid with obstacles? (Dynamic Programming)
Can someone tell me what am I doing wrong?
Problem: https://codeforces.com/contest/22/problem/B
Editorial: https://codeforces.com/blog/entry/507 ( I followed the DP solution O((n*m)^2) )
Eg:
...
2
votes
3answers
303 views
Selecting items from two arrays without duplicate indices to get maximum sum
Given two arrays both of length n, you have to choose exactly k values from the array 1 and n-k values from the other array, such that the sum of these values is maximum, with constraint that if you ...
1
vote
0answers
27 views
Determining the DP subproblem given a problem
I'm reviewing DP and I was wondering the intuition behind determining the subproblems for some DP problems.
For example, consider 2 similar problems.
Given a set of 1, 2, and 3 steps you can take, ...
0
votes
0answers
28 views
count all possible paths of length n in an undirected graph with use of dynamic programming [duplicate]
Given is an infinitely large grid graph. Use dynamic programming to calculate the number of possible paths
of a given length n from a given start node, so that fjor every path applies:
a) no vertex ...
0
votes
1answer
49 views
How to solve this job scheduling programming problem?
I am trying to solve this question. The question is a variation of job scheduling. There are n processes given to you with their execution time Ti and individual ...
2
votes
2answers
788 views
Split array into contiguous subarrays of approximately same sums
My question is similar to this splitting question, but my objective function is different.
Looking for an algorithm to split array of $n$ positive (integer) numbers into $N$ contiguous non-empty ...
0
votes
0answers
23 views
What does 'recursion with no explicit stages' mean in relation to dynamic programming?
I have the following excerpt from one of my assignments, essentially asking me to build on a previous formulation. However, while I can think of improvements, I have no idea if they fit the 'no ...
2
votes
1answer
36 views
Shrinking Item 0-1 Knapsack problem
I have encountered a variant of the knapsack problem with shrinking items.
Effectively, it is a 0-1 knapsack problem where the initial weight of each item is $W(n)+V(n)$ and their value is $V(N)$, ...
3
votes
2answers
61 views
Maximize number of museums visited in a day
Given a list of museums, their opening hours and time needed to visit each, make a schedule such that a tourist visits maximal number of museums in a given day.
Suppose that no time is needed in ...
