JOIN
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings View: Flat (newest first)  | Threaded  | Tree Previous Thread  |  Next Thread Forums Tutorial Discussions Dynamic Programming: From novice to advanced Upper-Intermediate: I am having a hard time implementing the pseudo-code in java
 Upper-Intermediate: I am having a hard time implementing the pseudo-code in java | Reply Will someone please implement the Upper-Intermediate pseudo-code in Java? Thanks.
 Re: Upper-Intermediate: I am having a hard time implementing the pseudo-code in java (response to post by kasavbere) | Reply Excerpts from the pseudocode are present as comments.`/** * Find the shortest path from vertex 0 to vertex N-1 or state that such a path doesn't exist where the graph is represented by the adjacency matrix * dist[i][j], and the cost of passing through vertex i is cost[i] and * the money available for the trip is M. * @param M * @param dist * @param cost * @return */ public int shortestPath(int M, int[][] dist, int[] cost) { int n = cost.length; int mSize = M + 1; //Set states(i,j) as unvisited for all (i,j) boolean[][] visited = new boolean[n][]; for (int i = 0; i < n; i++) { visited[i] = new boolean[n]; } //Set memo[i][j] to Infinity for all (i,j) int[][] memo = new int[n][mSize]; for (int i = 0; i < n; i++) { memo[i] = new int[mSize]; Arrays.fill(memo[i], Integer.MAX_VALUE); } memo[0][M] = 0; int lastK = -1; int lastL = -1; while (true) { // Among all unvisited states(i,j) find the one for which memo[i][j] // is the smallest. Let this state found be (k,l). int k = -1; int l = -1; int min = Integer.MAX_VALUE; for (int i = 0; i < memo.length; i++) { for (int j = 0; j < memo[0].length; j++) { if (visited[i][j]) { continue; } if (memo[i][j] < min) { k = i; l = j; min = memo[i][j]; } } } if (k == -1) { break; } if ((k == lastK) && (l == lastL)) { break; } lastK = k; lastL = l; for (int p = 0; p < n; p++) { // neighbors have dist < inf if (dist[k][p] == Integer.MAX_VALUE) { continue; } if (visited[k][p]) { continue; } visited[k][p] = true; int c0 = l - cost[p]; //If (l-S[p]>=0 AND // memo[p][l-S[p]]>memo[k][l]+Dist[k][p]) // Then memo[p][l-S[p]]=memo[k][l]+Dist[k][p] if ((c0 >= 0) && ((memo[p][c0] == Integer.MAX_VALUE) || (memo[p][c0] > (memo[k][l] + dist[k][p])))) { memo[p][c0] = (memo[k][l] + dist[k][p]); } } } //Find the smallest number among memo[N-1][j] (for all j, 0<=j<=M); //if there are more than one such states, then take the one with greater //j. If there are no states(N-1,j) with value less than Infinity - then //such a path doesn't exist. int min = Integer.MAX_VALUE; for (int j = M; j > -1; j--) { if (memo[n - 1][j] < min) { min = memo[n - 1][j]; } } // shortest path (which is the sum of the distances) for which total cost < M return min; }`
 Re: Upper-Intermediate: I am having a hard time implementing the pseudo-code in java (response to post by nkin) | Reply Isn't the upper intermediate problem same as intermediate problem? It is just that instead of maximizing the number of apples that can be collected, we are just trying to minimize the cost at each vertex?
 Forums Tutorial Discussions Dynamic Programming: From novice to advanced Upper-Intermediate: I am having a hard time implementing the pseudo-code in java Previous Thread  |  Next Thread