Questions about problems that can be solved by combining recursively obtained solutions of subproblems.

learn more… | top users | synonyms

2
votes
2answers
36 views

Given a set of numbers (negative or positive), and a maximum weight w, find a subset that is maximal whose sum is less than w

The aim of this problem is to find a subset (need not be consecutive) of a given set such that the sum is maximal and less than some given number $w$. (Note, we are trying to find a subset that is ...
1
vote
2answers
36 views

Getting speed difference between signal comparison using Dynamic Time Warping

I understand that Dynamic Time Warping is an algorithm to find a matching between two signals with different length and speed But is there a possible way to find the speed difference between the two ...
-1
votes
1answer
100 views

Are basic CS algorithms used in machine learning?

I have read some articles which state that basic algorithms such as dynamic programming , graph algorithms etc are not required int machine learning fields such as deep learning , reinforcement ...
2
votes
0answers
41 views

can we solve dynamic knapsack problem using Memoization approach?

As we know Dynamic programming has two techniques. Bottom up dynamic programming approach. Top down memoization approach Normally dynamic knapsack problem is solved using Bottom up dynamic ...
-1
votes
0answers
29 views

Find number of pairs [duplicate]

I have an array A of integers. I want to find possible number of pairs of non-intersecting sub-array which don't have any element common in them. For example A={1, 2, 1, 2} then correct subarrays(1-...
0
votes
1answer
36 views

Is there Any difference between dynamic programming vs branch-bound vs delayed column generation

I was reading about cutting stock problem https://en.wikipedia.org/wiki/Cutting_stock_problem , this is best solved using dynamic programming but wiki page mentions 2 other techniques names Branch-...
0
votes
1answer
53 views

Discrete optimisation in 5 variables

I need to solve the following optimisation problem and I can't come up with any solutions. Is there any algorithm to solve this type of problem. I tried to think of a greedy algorithm or brute force, ...
2
votes
1answer
227 views

Finding all soldier wins

Consider the following game (see also this question): One day a castle is attacked at sunrise (by surprise) by n soldiers. Each soldier carries a canon and a rifle. The castle has strength s. On ...
0
votes
1answer
73 views

Understanding The Mapping Of Edges to Nodes In A Graph Theory Problem

I am really confused with this problem. Here's the problem: You have $N$ points numbered $1$ through $N$,inclusive, and $N$ arrows again numbered $1$ through $N$,inclusive. No two arrows start at ...
1
vote
0answers
32 views

Knuth Yao DP Speedup - Cutting Sticks

There's a problem called Cutting Sticks - we start with one stick and n points where it needs to be cut. Cutting a stick costs the length of that stick. Of course, we want to minimize the toal cost. ...
4
votes
1answer
45 views

Two recurrences for the change-making problem with repetition

The change-making problem with unbounded repetition is: Input: Unlimited quantities of coins with values $x_1, \ldots, x_n$; and an amount $v$. Output: Can the given $v$ amount of money be ...
2
votes
0answers
39 views

Does the Longest Common Subsequence problem reduce to its binary version?

I am working on a problem regarding the Longest Common Subsequence (LCS) of two strings, and I was wondering if there is any reduction from the general case of LCS to its binary version, i.e. by ...
0
votes
0answers
42 views

Figure out recursive function for this problem

I'm trying to solve this problem whole day. The result should be dynamic programming algorithm but the first thing I need is to find out recurrent function. There is N students (N is even) in class. ...
0
votes
2answers
50 views

With Memoization Are Time Complexity & Space Complexity Always the Same?

I am studying Dynamic Programming using both iterative and recursive functions. With recursion, the trick of using Memoization the cache results will often dramatically improve the time complexity of ...
0
votes
1answer
38 views

Maximize cost in graph with variable costs

Consider the following problem. A prisoner eats once a day, he can either have a low, or a high calorie dish. In order to be allowed to eat the high calorie dish, he must not have eaten the previous ...
1
vote
0answers
38 views

Josephus Problem - A faster Solution

I came through Josephus problem a little while ago. Problem is stated as follows : "People are standing in a circle waiting to be executed. Counting begins at a specified point in the circle and ...
1
vote
0answers
38 views

Solving a Knapsack problem with a special structure

I have a set of $N$ items to fill a knapsack with maximum capacity $W$ and the maximum number of items that the knapsack can carry is $N_{m}$ items. The problem can be formulated as following: max $\...
2
votes
1answer
76 views

Reccurrence for the game of pile of stones

I am trying to solve this question from Project Euler for past few days: Divisor game. The problem is as follows: Two players are playing a game. There are $k$ piles of stones. When it is his turn ...
0
votes
0answers
20 views

Particle locating/collision prediction in bounded (two-dimensional) environments

I believe that many physics engines, particle simulators, and even video games use discrete-event simulation to determine where a particle or object is at any moment, and the direction in which it is ...
7
votes
2answers
124 views

What is the intuition on why the longest path problem does not have optimal substructure?

I was learning about longest paths and came across the fact that longest paths in general graphs is not solvable by dynamic programming because the problem lacked optimal substructure (which I think ...
0
votes
0answers
30 views

Find cheapest path from 1st city to the $n$th city

The title may be a bit misleading, but this is essentially a DP problem. The problem is that we have $n$ cities labeled from $1, ... n$ and we are trying to find the cheapest way to travel from 1 to $...
2
votes
1answer
37 views

What is the formal justification for the correctness of the second formulation of rod cutting DP solution

CLRS on section 15.1 3rd edition has a good discussion of the rod cutting problem. I will add a description at the end of the question for reference. Define $r_j$ to be the optimal way to cut a rod ...
2
votes
1answer
40 views

Orderability of Belief States in a POMDP?

Consider a POMDP with integer states $1,2,\ldots,N$, where $N$ is finite. We thus have a complete order over the states. It seems reasonable to think that belief states for this POMDP may be ...
1
vote
0answers
24 views

Does Optimal Substructure implies Convexity and vice versa?

In undergraduate CS, Dynamic Programming problems are often related to Overlapping Optimal Substructure (https://en.wikipedia.org/wiki/Optimal_substructure). Dynamic Programming is also often used in ...
3
votes
1answer
43 views

Why can't we run Bellman Ford from the source and relax edges out from the neighbours recursively and do a single pass through the edges?

At each $k$ th iteration of BF, we can are guaranteed to have computed the shortest paths that are at most $k$ long. That makes perfect sense me. If we relax a set of edges $k$ times, then we for sure ...
2
votes
3answers
205 views

Cutting yarn into integer-length pieces to maximize profit based on known prices for each length

My classmates and I were working on a problem on our introduction to algorithms homework, but we are having a lot of trouble wrapping our heads around it. Below is the problem: We are given a ...
1
vote
1answer
56 views

Is it possible to solve the coin denomination problem using a 1-D array?

In an algorithm book it said that to solve the coin denomination problem via Dynamic Programming approach a 2-D array is needed: Exercises 8.4 #9 Is it not possible to do this using a 1-D array. I ...
1
vote
1answer
32 views

Shuffled Strings Dynamic Programming [closed]

So I have this question: A shuffle of two strings X and Y is formed by interspersing the characters into a new string, keeping the characters of X and Y in the same order. Example would be ...
2
votes
1answer
111 views

Trying to understand this Dynamic Programming solution

The problem is as follows. Minimize the sum of absolute differences between a matching of $n$ values from two sets, $A=\{a_1,a_2,\cdots, a_n\}$ and the set $B=\{b_1, b_2,\cdots, b_m \}$, with $n\leq ...
2
votes
1answer
23 views

First Harshad number with given sum

How can we compute the least Harshad number with given sum of decimal digits $S$? Harshad number in base 10 is any number divisible by sum of its decimal digits. I think that some kind of dynamic ...
1
vote
1answer
67 views

What type of knapsack problem is this?

I need to choose the highest value combination of items given a specific set of constraints. These constraints are: Exactly 6 items from group A and 2 items from group B must be selected. Items in ...
3
votes
1answer
110 views

Tile Problem : Dynamic Programming

Came across the following tile problem : ...
3
votes
2answers
125 views

Minimize a sum with a weight constraint

We are given N sets, each of which has a finite number of pairs $(x_i,y_i)$. $M_1=\{(0,0), (x_{1,1},y_{1,1}), ...\}$ ... $M_N=\{(0,0), (x_{1,N},y_{1,N}), ...\}$ ...
1
vote
1answer
48 views

Check if a tree is formed by 3 subtrees with given number of nodes

I have run into a contest problem (ACM like) that sounds like this: Input: a tree of $N$ nodes; integers $X,Y,Z$ such that $X+Y+Z=N$ Question: Can the tree be partitioned into three trees of $X,Y,Z$ ...
15
votes
3answers
568 views

Largest sum divisible by n

I asked this question on StackOverflow, but I think here is a more appropriate place. This is a problem from Introduction to algorithms course: You have an array $a$ with $n$ positive integers (...
3
votes
0answers
36 views

How to compare A* with DP approach in finding shortest Path?

Consider a hypercube defined over $n$ dimensions where the edges are associated to strictly positive weights, and nodes are marked with $n$ bit-strings, e.g. the source is marked as (0,0,0) in a 3-...
0
votes
1answer
29 views

DP - Removing contiguous subsequences from a sequence optimally

I was asked this question a while ago and I'm very stuck: You have a sequence of 0's and 1's, and you can perform one ...
0
votes
0answers
41 views

Longest double increasing subsequence (LIS variant)

I'll start with the definitions:Let $S = s_1s_2...s_n$ be a sequence of $n$ integers. A double increasing subsequence of $S$ is a sequence $P=p_1p_2...p_k$ (not necessarily continuous) where for each $...
3
votes
1answer
107 views

Dijkstra's algorithm to compute shortest paths using k edges?

I am aware of using Bellman-Ford on a graph $G=(V,E)$ with no negative cycles to find the single-source single-destination shortest paths from source $s$ to target $t$ (both in $V$) using at most $k$ ...
6
votes
2answers
806 views

Why is the dynamic programming algorithm of the knapsack problem not polynomial? [duplicate]

The dynamic programming algorithm for the knapsack problem has a time complexity of $O(nW)$ where $n$ is the number of items and $W$ is the capacity of the knapsack. Why is this not a polynomial-time ...
3
votes
1answer
99 views

Finding a maximal set of nonintersecting line segments in a unit circle

Let P be a set of n points that divides the unit circle into equal pieces. Let S be a set of m line segments such that their end points are points in P. The points aren't unique per line, meaning ...
1
vote
1answer
41 views

Travelling plan between two places

There is a class of DP related problems where you have a set of consecutive steps, say $1 \ldots n$, and two places e.g. $A$ and $B$. At each step $i$ there are two choices: stay where you are or ...
3
votes
1answer
79 views

Proof for Minimum number of insertions to convert a string to a palindrome

For the problem "Find the minimum number of insertions to convert a string $S$ to a palindrome", a recurrence relation usually given is: $$ c[i,j] = \begin{cases} c[i+1,j-1] & \text{if } S[i] = S[...
1
vote
1answer
81 views

Number of submatrices, of a base matrix derived from an array, with a particular sum

Given an N sized array A of unsorted integers and an integer K, derive a square matrix M of order N where $ M_{ij} = A_i * A_j $, and return the number of sub matrices of M where the sum of all of its ...
3
votes
1answer
155 views

Find a maximum sum in matrix, subject to special constraint

I have a matrix of size $N \cdot M$ filled with integer values $A[i][j]$. I want to choose some numbers so that their sum is maximal. But there is one very important constraint. If I choose numbers in ...
3
votes
1answer
54 views

Remove contiguous subsequence so the remaining numbers will created a sorted sequence

You are given $N$ numbers. Remove contiguous subsequence of those numbers, so the remaining numbers will create a sorted sequence. For example, if the sequence is $5$, $7$, $8$, $2$, $1$, $9$ then we ...
0
votes
1answer
26 views

Help coming up with a solution to a combinatorial problem

So here is the problem: Say I want to find the only possible combinations to find the sum of a specific number using only the numbers 1, 2, & 3 with a specific number of additions. I know this ...
5
votes
0answers
115 views

Can the solution to a POMDP be found using linear programming?

It is known that Markov decision processes (MDPs) can be solved using linear programming (see page 24 of Carlos Guestrin's PhD dissertation). The linear program is: $$min_{V(x)} \sum_x \alpha(x)V(x)\\...
1
vote
0answers
128 views

Dynamic programming: speed of top down vs bottom up approaches

I have just completed a dynamic programming exercise on LeetCode (Coin Change). I tried a top down approach, but it failed for the larger inputs, whereas the bottom up approach worked for all inputs. ...
0
votes
1answer
44 views

Is the terminology of the word optimal substructure same for divide-conquer and dynamic programming technique?

why do we use the word optimal in case of optimal sub-structure , I guess in case of divide and conquer also we have sub-problems and they too when merged together provide the solution for entire ...