» Optimum path in a graph to maximize a value
Optimum path in a graph to maximize a value
|April 27, 2014
Posted by forumadmin
I’m trying to come up with a reasonable algorithm for this problem:
Let’s say we have bunch of locations. We know the distances between each pair of locations. Each location also has a point. The goal is to maximize the sum of the points while travelling from a starting location to a destination location without exceeding a given amount of distance.
Here is a simple example:
Starting location: C , Destination: B, Given amount of distance: 45
Solution: C-A-B route with 9 points
I’m just curious if there is some kind of dynamic algorithm for this type of problem. What the would be the best, or rather easiest approach for that problem?
Any help is greatly appreciated.
Edit: You are not allowed to visit the same location many times.
More Related Questions
- What is dynamic programming algorithm for finding a Hamiltonian cycle? What is dynamic programming algorithm for finding a Hamiltonian cycle in a undirected graph?
I have seen somewhere that there exists a algorithm with O(n*2^n) time complextity Asked […]
- all solutions to change making with dynamic programming I was reviewing my handouts for our algorithm class and I started to think about this question:
Given different types of coins with different values, find all coin configurations to add […]
- How many distinct expressions are possible? I came across the following practice problem.
You are free to put any parentheses to the expression anywhere you want and as many as you want. However it should be a valid expression […]
- Whats the time complexity of this algorithm for Palindrome Partitioning? Palindrome Partitioning
Given a string s, partition s such that every substring of the
partition is a palindrome. Return all possible palindrome
partitioning of s.
Personally I […]
- Dynamic Programming: USACO Optimal Milking I have been looking at some USACO gold level algorithm problems, and I need someone to help explain the solution of this problem to me. Here is the problem, and the solution is below:
- Finding least number of moves I have the following problem statement:
Given a number n (1 < n < 10^9), what is the least number of
mathematical operations from the set (divide n by 2, divide n by 3,
- Good Java graph algorithm library? Has anyone had good experiences with any Java libraries for Graph algorithms. I've tried JGraph and found it ok, and there are a lot of different ones in google. Are there any that people […]
- Algorithm to minimize vertex distances – Dwarf Fortress I play Dwarf Fortress game. And the main challenge for me is to design layout of the fortress efficiently. Meaning, that each industry flow should be as dense as possible, to minimize the […]
- Best Graph Drawing Algorithm For Hierarchical Data? I have a collection of directed acyclic graphs that are nearly trees, in the following sense: each graph has a root, and the vertices are organized into levels such that if v1 and v2 are […]
- Drawing Directed Acyclic Graphs: Minimizing edge crossing? Laying out the verticies in a DAG in a tree form (i.e. verticies with no in-edges on top, verticies dependent only on those on the next level, etc.) is rather simple without graph drawing […]