All Questions
Tagged with recursive-algorithms dynamic-programming
25
questions
0
votes
1
answer
123
views
Knapsack problem with overload
Let $N = \{1, 2, \ldots, n\}$ denote a set of items, $w \in \mathbb{R}_{++}^N$ a vector of weights, $c > 0$ a constant and $x \in \{0, 1\}^N$ a decision variable.
The objective is to minimally ...
- 771
1
vote
1
answer
303
views
closed-form solution to a recursive function
My question is about this problem I made up:
'I have a height of unit length, and m glass balls. Dropping a ball higher than some unknown height, h, always breaks them, and dropping a ball lower never ...
- 13
4
votes
1
answer
207
views
Brick wall with maximum height 3
Given n same-sized rectangular bricks. We want to build a wall with these constraints:
All bricks should be horizontal.
We can put a brick on two other bricks, such that the middle of the top brick ...
- 51
1
vote
0
answers
128
views
Dynamic Programming question - n floors and m boxes
Q: Given a building with $n$ floors, each floor $i$ has $c_i$ boxes in it. You need to find a way to store all the boxes in at most $m$ floors. Moving boxes from one floor to another is allowed only ...
- 332
0
votes
1
answer
291
views
Minimum cost in a 2D matrix
In my last interview, I was asked a question for which optimal approach I am still not able to figure out.
Given a 2D matrix, with n rows and ...
- 1
0
votes
1
answer
1k
views
Dynamic Programming Cheapest Train Ride Question
I am struggling with the below dynamic programming practice problem and I am hoping someone can help. The problem states:
"You want to go from station 1 to station n by rail. The train fare from ...
6
votes
1
answer
545
views
Egg dropping problem binomial coefficient recursive solution
I have a question about the binomial coefficient solution to the generalization of the egg dropping problem (n eggs, k floors)
In the binomial coefficient solution we construct a function $f(x,n)$, ...
- 496
5
votes
0
answers
121
views
Partition problem where partition are in increasing order.
For given $n$ and $S$, how many possible combinations are there such that:
$x_1 + x_2 + .. + x_n = S $ $\forall i, x_i \leq x_{i+1}$ $\&$ $x_i \geq 1$
For example, if $n$ = 3 and $S$ = 5, there ...
- 51
3
votes
1
answer
457
views
Dynamic Programming problem palindrome
I am stuck with the following problem:
Given a string of characters $w$, we want to know the minimum number of characters that we must add to $w$ in order to convert this string in a palindrome (note ...
- 3,887
0
votes
1
answer
139
views
what is the complexity of recursive summation
Can someone tell me the exact complexity of this recursion ? this is actually formula for below question ( solved in recursive brute force way )
There is n steps stairs and a person standing at the ...
- 1
2
votes
2
answers
2k
views
Divide set into two subsets of equal sum and maximum this sum
Original Question: https://stackoverflow.com/questions/47492444/create-two-sub-lists-from-given-list-of-integers-with-equal-sum-and-maximize-thi
You are given a list S of positive integers. You are ...
- 195
0
votes
0
answers
497
views
Proof for greedy algorithm on doubling currency?
I have a currency where each subsequent coin is twice as valuable as the one before it.
I need to prove that for any amount of change needed, the greedy algorithm for making change (always choosing ...
- 1
3
votes
1
answer
423
views
How to determine the optimal permutation to get to a result with the minimum steps
I am not a mathematician. I need to be able to frame my problem so I would like guidance on what type of problem this is and perhaps guidance on how to solve it.
I have patients with food allergies. ...
- 141
0
votes
1
answer
324
views
Question regarding coin change algorithm (DP and greedy)
The question goes something like this:
Suppose you are living in a country where coins have values that are powers of p, V = [1, 3, 9, 27]. How do you think the dynamic programming and greedy ...
- 23
3
votes
1
answer
686
views
Is this the correct minimum number of coins needed to make change?
The Problem: On Venus, the Venusians use coins of these values [1, 6, 10, 19]. Use an algorithm to compute the minimum number of coins needed to make change for 42 on Venus. State which coins are used ...
- 1,884