The dynamic-programming tag has no wiki summary.
2
votes
2answers
52 views
find the largest integer less than a number
I'm trying to figure out this problem for few hours now. please help.
Define $$\text{PCOM}(a,b,c) := \{ax + by + cz : x, y, z ≥ 0\}.$$
Given integers $t > c > b > a > 1,$ I need help ...
0
votes
1answer
28 views
“Location to location” algorithm?
Lets say I have two locations, each one with X, Y, Z, and a int. Each location represents one cube in a 1000 x 1000 world. Lets say I had one location at 500, 343, 284, with an int 1. Another one at ...
0
votes
0answers
54 views
Algorithm for Dynamic Programming of Kleinberg Book
I need help for this about answer and program of it with C.
From Kleinberg & Tardos's (2006) Algorithm Design, pp. 334–335:
29. Let $G = (V , E)$ be a graph with $n$ nodes in which each pair ...
1
vote
1answer
22 views
Dynamic Programming Trouble, Optimizing time
A robot goes from terminal to terminal collecting bolts. The robot needs to collect at least $m$ bolts and there are $n$ terminals. Terminal $i$ gives the robot a certain number of bolts denoted by ...
1
vote
3answers
117 views
Give an $O(n^3)$-time dynamic programming algorithm for the given problem
There are n cities in a country. Every two cities u and v are connected by a
bi-directional highway that takes $l(u,v)$ hours to drive through. A car with gas tank capacity $c$ can only travel for $c$ ...
0
votes
0answers
42 views
Solving a specific discrete dynamic programming problem by hand (example inside)
I would be grateful if someone could help me out with an assignment which I am pretty sure is erroneous.
\begin{aligned}
min & -\sum_{j=0}^{N-1}c(1-u(t_j))y(t_j) & \\
NB \qquad ...
0
votes
0answers
32 views
DP formulation for the shape of Water-drop?
There are different suggestions for the shape of water-drop such as Joukowskis and Piriform parametrization. I am trying to understand how the water-drop-shape is deduced.
Suppose a trivial case ...
0
votes
0answers
42 views
Random rectangles placement with minimal overlap and good dispersion.
I have a Big Rectangle (axis-oriented) containing a lot of Small Rectangles (with the same orientation of the parent and with a fixed size of 82x176 pixels).
Now I have a Small Rectangle which is ...
1
vote
1answer
51 views
Dynamic Programming— Variable Width Bin (Equi-Depth) Histogram
Given some data, and a fixed number of bins (k)-- How can I design a Dynamic Programming algorithm that minimizes the largest difference between bin sizes?
In other words, with a set number of bins ...
0
votes
0answers
53 views
Is Euler Equation in DP the same as the Euler-Lagrange Equation?
Euler equation is often associated to Euler-Lagrange equation but I got an impression during the lecture that Euler equation is not the same as Euler-Lagrange. Please help me to understand their ...
2
votes
1answer
152 views
How to solve this LP problem as a Dynamic Programming problem?
The standard form LP problem is
$$\min -3x_1-7x_2-10x_3 \text{ s.t. }$$
$$x_3\leq 2$$
$$40x_3+40x_2+20x_1\leq 180$$
$$x_1,x_2,x_3\geq 0$$
My last lecture covered the Bellman equation ...
0
votes
1answer
30 views
Cost-to-go form of Dynamic Programming algorithm?
My lecture of Mat-2.3148 (Finnish) defines dynamic-programming-algorithm so that$J_N(x_N)=g_N(x_N)$ and $J_k(x_k)=\min_{u_k}\left\{g_k(x_k,u_k)+J_{k+1}(f_k(x_k,u_k))\right\}$ where
the state ...
1
vote
1answer
110 views
What's the optimal strategy of this dice game?
I'm working on dynamic programming problems this week. The following is a dice game. I'm trying to find the optimal strategy using dynamic programming.
The game's description :
The player rolls ...
2
votes
2answers
125 views
Pseudocode for view the combinations .
Can you help me please with a program which can calculate the number of combinations and to view it ? A pseudocode ? Is there something like a code - to program it ?
thanks :)
0
votes
1answer
69 views
Prove problem reduces to 0-1 knapsack problem
http://community.topcoder.com/stat?c=problem_statement&pm=12329
I was practicing on TopCoder and found this problem. I solved it by noticing that it looks a little like the 0-1 knapsack, but I do ...
3
votes
2answers
130 views
What's the optimal strategy of this dice game?
I'm working on a dynamic programming problem. I want to find the optimal strategy and simulate it.
The game's description:
The player rolls two dice.
If the numbers shown by the two dice are ...
1
vote
0answers
31 views
maximising the frequency of mode.
I have 4 numbers 5,5,3,1. Now I have the number 5, which I can distribute in any manner to ...
0
votes
1answer
322 views
What is a subproblem graph in dynamic programming parlance?
I know what dynamic programming is but I do not really understand the concept of subproblem graph for a dynamic programming ? How are they useful ? When solving problem by dynamic programming should ...
