Dynamic programming builds solutions from solutions to simpler subproblems. It's closely allied to recursion, but dynamic programming algorithms are formulated as iteration usually over a very regular datastructure.

learn more… | top users | synonyms

2
votes
2answers
82 views

How to retrieve policy after Dynamic Programming?

I'm working on a simple resource allocation problem, that I'm solving using backward DP. The full code is at: http://codereview.stackexchange.com/questions/123641/allocating-a-resource It works fine, ...
3
votes
1answer
239 views

Dynamic Programming - Largest arrangement of bookcases

I'm trying to solve a problem, so I'm not looking for code, but for similar algorithms so I can solve it myself. I am given n bookcases each with a size amount of books inside. I am to move some of ...
1
vote
1answer
63 views

Dynamic-programming matrix exercise

I'm practicing with dynamic programming and I'm trying to solve this exercise http://www.geeksforgeeks.org/collect-maximum-points-in-a-grid-using-two-traversals/ But I can't understand how to use ...
0
votes
1answer
131 views

Given an array of number, how to calculate to a target value

Chatting with a friend about a game we used to play, and thinking how to implement it in code. Here are the rules: Given a list of number e.g. {1,2,3,4} Try to use all the numbers from the list to ...
0
votes
1answer
150 views

How to find a subset of size k such that the minimum distance between values is maximum

Suppose I have a sorted array which contains n integers. How do I find subset of size k such that the minimum distance between all pairs of integers in the subset is maximized, I mean they are at ...
4
votes
0answers
549 views

Dynamic programming in Bin packing

Problem: Given a list L of objects of possible sizes from set S={1,2,4,8} and unlimited supply of bins of sizes 16 each and we have to use minimum possible numbers of bins to pack all objects of L. I ...
4
votes
0answers
293 views

Help/suggestions for Parallel assembly line scheduling (Dynamic programming)

I am working on a problem similar to the assembly line scheduling by dynamic programming.The issue is that unlike the classic problem where we have predefined stations now I only have information ...
1
vote
0answers
52 views

Select the sequence to minimize the cost

Lets say there is a delivery-boy who wants to distribute some food packets over N cities (1..N). We know the number Pi of packages that are to be delivered at city i. We know the distance between ...
0
votes
0answers
46 views

Algorithm: Calculate average time in given time frame

I have a complex problem to solve. Problem Statement: I have a list of cities: Lets say New York, LA Las Vegas California The list of cities is limited, not more than 10. Now there are peoples ...
0
votes
0answers
44 views

Dynamic programming vs branch-and-bound for the knapsack problem

I have to implement a program that solves the 0-1 knapsack problem, where the weights and values of all items are nonnegative integers. We went over two methods in class: dynamic algorithms (...
0
votes
0answers
151 views

scrabble solving with maximum score

I was asked a question You are given a list of characters, a score associated with each character and a dictionary of valid words ( say normal English dictionary ). you have to form a word ...