Questions tagged [dynamic-programming]
Questions about problems that can be solved by combining recursively obtained solutions of subproblems.
948
questions
0
votes
0
answers
31
views
Dynamic Program to find well formed set in a rooted tree
You are given a rooted tree $T=(V,E)$ with $n$ nodes and the root $r$. Each node $u\in V$ has an integer label $l(u)$. Suppose $S⊆V$ then $S$ is well-formed if for every $u,v\in S$ if $u$ is an ...
- 139
-1
votes
0
answers
22
views
Backpack assigment
Can you help me solve this problem. Names of items NAME, sizes SIZE and values VALUE are given. Using dynamic programming, find the optimal filling of backpacks of size M. NAME = {A, B, C, D, E}, SIZE ...
- 1
0
votes
0
answers
11
views
Dynamic programming problem for minimum cost tower placement
I have an algorithmic problem in which I have a highway that is a straight line of length n and a set of unique respective costs for construction of a radio tower for each mile on the highway. I am ...
1
vote
0
answers
37
views
How do i make a 2d array as same as i possibly can with another one?
Say i have an 2d array A of nxn size, int values already given for each item.these values can be the same or different.
There's gonna be another nxn array B being input.
I can only interchange one row ...
- 11
0
votes
0
answers
12
views
Better implementations for this dynamic program to solve optimization problem?
In the code below, I describe a problem and provide a backtracking implementation in Python that solves it:
...
- 181
0
votes
0
answers
16
views
Optimize clothing in RPG considering set bonuses
In role playing games, switching equipment for better is a common procedure. My question is to find an algorithm that can optimize linear combination of stats the equipped gear gives - this is exactly ...
- 1
0
votes
0
answers
19
views
Knapsack with weight swaps
I have a problem that is 0/1 knapsack, but you are also able to swap the weight of 2 items up to k times. I came up with a O(nkc) solution, but I am looking for a faster o(n*c) solution. I think the ...
0
votes
1
answer
30
views
3 Processor Scheduling
A set of n independent tasks, each having integer execution times,
are to be executed using three identical processors. A task can be
executed in any of the three processors. Develop a sequential
...
- 1
0
votes
0
answers
24
views
Optimizing an Algorithm for Timestamp-Aware Partitioning of Data
My Problem
I'm currently dealing with an algorithmic problem that involves two input lists:
A list of natural numbers $[A_1, A_2, \dots, A_n]$ with $A_1, \dots, A_n \in \mathbb{N}$.
A list of triples ...
1
vote
0
answers
88
views
complexity of graph matching with order constraint
Given a graph with $n$ vertices and $m$ edges, $m \le {n \choose 2}$, we index the vertices from 1 to $n$, and denote every edge by $(l,r)$ where $1\le l < r \le n$.
Find the maximum $k$ such that ...
- 11
0
votes
0
answers
32
views
Find submatrix with sum as close to k as possible
What is the efficient algorithm to find a submatrix (must be rectangle) with a sum that is as close as possible to k? Matrix consists only of nonnegative integers. Iterating through all possible ...
- 1
0
votes
0
answers
24
views
Dynamic Programming for LCS problem
I understand that in Dynamic Programming approach the subproblems are solved in a particular order from smallest to largest. In LCS how the subproblems sizes are defined and in which order it is ...
0
votes
1
answer
58
views
CSES problem Two Sets II
Your task is to count the number of ways numbers $1,2,…,n$ can be divided into two sets of equal sum. For example, if n=$7$, there are four solutions:
${1,3,4,6}$ and ${2,5,7}$,
${1,2,5,6}$ and ${3,4,...
- 11
0
votes
0
answers
14
views
Feedback Vertex Set in graphs with bounded tree width using Dynamic Programming
What is the subproblem associated with this DP and what are the terms to calculate?
0
votes
1
answer
76
views
Matching points on a plane with maximum total weight
I have a set of points $P = \{p_1, \dots, p_m \}, \; 0 \le m \le 10^4$ on a plane of two colors (red and green). Each point has integer x-coordinate (all x-coordinates are different), and non-negative ...
- 95
1
vote
1
answer
44
views
In a directed graph, efficiently determine node reached after traveling k edges from the starting node
I am trying to solve a problem where I am given a directed graph with $n$ nodes where, from any given node, I can reach one and exactly one node. Nodes contain integers from $1$ to $n$. Starting at ...
- 13
1
vote
0
answers
31
views
Maximize sum of matrix after deleting K rows and K columns
You're given a m by n matrix filled with positive integers, as well as some integer k (0 <...
- 111
0
votes
1
answer
50
views
Efficient algorithm for finding the target sum
Task. Find such natural numbers a1,. . . , am , that none of them would be included in the list of excluded numbers, a1 + · · · + am = N and max{a1 , . . . , am} would be as small as possible. Numbers ...
- 1
0
votes
0
answers
15
views
1
vote
1
answer
46
views
Finding the subset of a dictionary that has the minimum edit distance to a given string
I'm looking for the most efficient way of solving an Levenshtein edit distance problem.
We are given as input:
A set of strings S of size ...
- 411
0
votes
0
answers
80
views
Best time to buy and sell stocks with multiple buy transactions are allowed and can sell all shares at once
I've been trying to solve a variation of this problem https://stackoverflow.com/questions/62389658/best-time-to-buy-and-sell-stocks-when-allowing-consecutive-buys-or-sells
You are given an input array ...
- 37
3
votes
1
answer
94
views
Path planning on 2D grid graph to maximize the neighboring grid points of a path: Can we do better than brute DFS?
On a finite 4-connected grid graph, given the source point and destination, it is allowed to consecutively move in one of the four orientions (up, down, left or right) to form a path. We get 1 bonus ...
- 31
1
vote
1
answer
148
views
knapsack with graph connectivity constraints
I am looking for a variant of the knapsack problem in which the items are nodes in an undirected graph, and the knapsack must be filled with a connected subgraph. Formally:
The input is an undirected ...
- 5,730
1
vote
1
answer
74
views
How can this problem be solved in $O(n^{3/2}log(n))$ time?
I can solve the following problem by Jeff Erickson in $O(n^3)$(and maybe in $O(n^2logn)$) time but how is the $O(n^{3/2} log(n))$ time solution possible?
Let $D[1 .. n]$ be an array of digits, each ...
- 13
2
votes
1
answer
61
views
Minimal set of elements needed to satisfy property counts
I have a friend who works in education. Sometimes, they need to create customized "word lists" to help students practice reading. These lists are limited in length, and must contain ...
-2
votes
1
answer
57
views
1
vote
1
answer
89
views
Longest Increasing Co-Prime Subsequence?
This is a made up question not seen somewhere so I am not sure if a good solution exists but here it is anyways.
Given an array $ A $ of $ N $ non-negative integers, find the longest non-decreasing ...
- 105
1
vote
1
answer
51
views
Minimum coins to make change when real numbers are allowed
There is the classical version of the minimum coins to make change problem where the change and the set of coins available are all integers. Given an infinite amount of each type of coin, we're asked ...
- 305
4
votes
1
answer
109
views
Telescope Scheduling Predecessors
In Algorithm Design and Applications by Michael T. Goodrich and Roberto Tamassia Chapter 12.3 there is a presentation of a problem called the Telescope Scheduling problem.
Given n requests each with ...
- 43
1
vote
0
answers
22
views
Formulating a bottom-up dynamic programming premise for a board game
The game being played here has the following rules, played be a singular player: there is a 5x5 board, where some tiles are highlighted and some are not. From here, the player can highlight the blank ...
- 11
1
vote
0
answers
44
views
Dynamic Programming: Counting *cycles* consisting of distinct numbers
I was thinking about this question and thought about it for quite a while but couldn't come up with an answer.
Firstly, we fix two sets $R$ and $S$. We consider "cycles", which are tuples in ...
- 111
0
votes
0
answers
26
views
Optimality in greedy task
There is a well-known problem of the best time to buy and sell stock. Assume now we have two arrays, SELL and BUY. Each time SELL[i] > BUY[i]. Assume we have initial budget B, and we can buy any ...
- 151
2
votes
2
answers
99
views
Zero sum game: dp recursion strategy
Trying to solve the zero-sum problem described here, where two opponent players at each turn can choose to collect 1, 2 or 3 stones with different values, with the objective of getting more points at ...
- 121
0
votes
1
answer
72
views
How to cover elements with minimum amount of elements
I'm trying to create a game but I am having some difficulties in coming up with a suitable algorithm for my problem.
I have elements from 1 to n and I am trying to cover all of the elements using the ...
- 11
0
votes
0
answers
65
views
House Robber Problem Variation with Risk/Cost to Rob Each House
I came across a modification of the classic house robber problem where there is a cost to robbing each house, and we want to maximize the amount robbed using the array (exactly as in the original ...
1
vote
1
answer
27
views
Constrained precedence parsing
This is a simple variation on precedence parsing for which I haven't been able to prove the existence of an efficient algorithm. Is this a known problem?
The setup is as follows: we are given $n$ ...
- 531
0
votes
0
answers
29
views
Algorithms for finding number of sequences with length N and displacements less than k
The sequences are made up of only digits. A displacement is defined as pair $(i, j)$ such that $i > j$ and $A[i] < A[j]$. For example, 423 has 2 displacements.
The question is to find the number ...
0
votes
1
answer
58
views
Why does the non-adjacent sum problem have optimal substructure?
In my algorithms class, my professor presented the problem of finding the largest sum of non-adjacent elements in an array. For example, if we have $[1,4,3,8,5]$ the largest sum of non-adjacent ...
- 1
-2
votes
1
answer
104
views
Find Number of subsequences such that bitwise OR is same as sum
Suppose there is an array having at most 10 elements between 1 to 10^18. Suppose the array has elements B1,B2,.Bn. We can choose sequence A1,A2,A3,..An such that 0<=Ai<=Bi. Count How many ...
- 1
0
votes
0
answers
31
views
Upper bound of traveling salesman problem via dynamic programming
For a set of $n$ cities, the total time to compute OPT (see Fomin & Kratsch, Chapter 1) is given to be
\begin{equation}
\sum_{k=1}^{n-1} O\left(\left(\begin{...
- 101
0
votes
0
answers
46
views
Is there a sorting program or formula to sort and place individuals in classes based on preferences
I am looking for a formula or program to help place people in classes based on their preferences.
The elements of the problem are:
There are 30 class choices a student can pick from.
There are 400 ...
- 1
1
vote
1
answer
393
views
Placing K gas stations among n cities to minimize distance
There are $n$ cities on a highway with coordinates $x_1$
, . . . , $x_n$ and we aim to build $K < n$ gas stations
to cover these cities. Each gas station has to be built in one of the cities, and ...
2
votes
1
answer
62
views
Checking forbidden moves in Renju
I am trying to detect forbidden moves for black in a game called Renju. First, here is an explanation of how Renju works.
Renju is a board game played on a 15x15 Go board. There are two players in the ...
2
votes
0
answers
75
views
Recurrence Relation for Longest Increasing Subsequence Problem
I am trying to solve the Longest Increasing Subsequence(LIS) Problem using different OPT Function than the one which normally used. I have been given this question as an extra credit and I have been ...
- 21
2
votes
2
answers
596
views
Select a subset of k intervals which form maximum length if we take union of these k intervals
Suppose we have $n$ intervals given in the form of (startTime,EndTime). I wish to calculate maximum length of the region that is exactly union of $1<=k<=n$ intervals.
Note that there are 2 cases ...
- 123
1
vote
2
answers
134
views
How do I find the most even combination for two arrays
I have two arrays that both contain $n$ elements (positive, non zero, not negative)
$\{x_1\dots x_n\}$
$\{y_1\dots y_n\}$
I want to pair them up optimally, one from each array, so that the pairs come ...
- 11
0
votes
1
answer
66
views
Compute the maximum length of an increasing digital subsequence given an array of digits
Consider the following exercise from chapter Dynamic Programming in the book Algorithms by Jeff Erickson.
Let $D[1 .. n]$ be an array of digits, each an integer between $0$ and $9$. A digital ...
- 1,564
1
vote
0
answers
139
views
Tabular Meta-Learning in RL
There are various meta-learning algorithms in RL that are proposed for settings when we have a (deep) neural network and the policy (or the value function) are parameterized as such.
Can these methods ...
- 175
0
votes
1
answer
54
views
Confused on Bellman Ford
We have a graph where we want to get from node u to v in the shortest path possible.
I understand how Bellman-Ford works when we have exactly i edges to go from u to v or at most i edges to get from u ...
1
vote
1
answer
92
views
Another Game Theory Problem
We have an array of integers of length N(even). A and B play a game where A selects a number followed by B without replacement until the array becomes empty(Both A and B select N/2 elements each). The ...
- 25