Tagged Questions

Dynamic programming is an algorithmic technique for efficiently solving problems with a recursive structure containing many overlapping subproblems.

learn more… | top users | synonyms

2
votes
0answers
181 views

Improving random memory access when random access is needed

The basic concept of what I am doing Complete coalition structure formation problem/Combinatorial auctions. Given a set of N agents, which disjoint subsets of the set of agents yields the best ...
2
votes
0answers
175 views

Recursive Relation Help for dynamic programming 2d Plane algorithm

So I've been working on an algorithm. The task I'm trying to accomplish is: consider a 2D plane there are targets that are randomly distributed between a y upper bound and lower bound. This set is T. ...
2
votes
0answers
288 views

Parenthesization that minimize values of an expression

I need to find a parenthesization for E= c1 O1 c2 O2 .... On-1 cn where c(i) are integers and O(i) could be + or *, that minimize the obtainable value through a parenthesization. I know that's ...
2
votes
0answers
690 views

Tallest possible tower built using stacking boxes

The problem I am trying to solve is called box stacking. Here is the description: Box Stacking You are given a set of n types of rectangular 3-D boxes, where the i^th box has height h(i), width w(i) ...
1
vote
0answers
39 views

Boolean Mode Where Match Query with Dynamic Against Values, using PHP MySQLi Prepared Statements

I want to query mysql with a Where Match query using mysqli prepared statements. The problem is the Boolean Mode AGAINST values, normally: (+value1 +value2 +value IN BOOLEAN MODE) but the problem ...
1
vote
0answers
61 views

Printing Balanced Partition

There are two arrays , say A & B. There are n entries in each of them , now we want to get minimum difference if we select either of each A & B for for ith entry. Exact problem here . I have ...
1
vote
0answers
103 views

Pseudo polynomial or fast solution for the relaxed subset-sum

I have an array A of positive integers [a0, a1, a2, ..., an] and a positive number K. I need to find all (or almost all) pairs of subsets U and V of array A such as: sum of all elements in U are ...
1
vote
0answers
132 views

USACO — Dynamic Programming — Longest Common Subsequence

I've used this recursive relation to solve this classic problem. Here it is: if (I == n || J == m) dp[I][J] = 0;<br> else if (x[I] == y[J]) dp[I][J] = dp[I+1][J+1] + ...
1
vote
0answers
152 views

Dynamic programming selecting tuples(size T) of nos with each not greater than k and sum S

Guys this is the question In a tournament, N players play against each other exactly once. Each game results in either of the player winning. There are no ties. You have given a scorecard containing ...
1
vote
0answers
242 views

Maximum Number of Rectangles to Fit in An Area [Competition , Not HW]

I have had this category of problems before, but never been able to solve it. The problem statement this time being : There are a given number of rectangles (different dimensions, given) , and a ...
1
vote
0answers
153 views

Pseudo polynomial or fast solution for the multiobjective subset-sum

I am looking for a fast solution for a multiple/multiobjective subset-sum problem. As aditional restraints (which make a litte easier to calculate IMO) we can assume that all values included in the ...
0
votes
0answers
32 views

closed form for the recurrance

This is the problem statement We have z numbers from 1 through z. Now we need to find the number of ways in which they can be permuted such that the sum of every pair of adjacent numbers is at ...
0
votes
0answers
35 views

There is an array of size n.One selects four values i,j,k,l such that 1<=i<=j<k<=l<=n

Then we calculate as follows .Add (A[i]+...+A[j]) and store them as variable p.Add (A[k]+...+A[l]) and store them as variable q.Then we find absolute difference between p and q. How to find out the ...
0
votes
0answers
36 views

What is the difference between dynamic programming and branch and bound?

I only know that by branch and bound, one can REDUCE the procedure to obtain a solution, but that only helps for problems which have a solution space tree....
0
votes
0answers
34 views

BUILDING BRIDGES DYNAMIC PROGRAMING

Probelm: There is a river that runs horizontally through an area. There are a set of cities above and below the river. Each city above the river is matched with a city below the river, and you are ...

1 2 3 4 5 … 8
15 30 50 per page