07.05.2012, 23:52 | #1 (permalink) |
Новичок
Регистрация: 04.03.2012
Сообщений: 9
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Репутация: 10
|
Помогите с программой
Билась над ней дня 2,ничего не придумала,все равно выводит минимальный цикл. Помогите кто может,что тут надо поменять?Программа на Java... Код:
import java.util.*; public class Cycle { public static int getCycle(int[][] dist) { int n = dist.length; int[][] dp = new int[1 << n][n]; for (int[] d : dp) Arrays.fill(d, Integer.MAX_VALUE / 2); dp[1][0] = 0; for (int mask = 1; mask < 1 << n; mask += 2) { for (int i = 1; i < n; i++) { if ((mask & 1 << i) != 0) { for (int j = 0; j < n; j++) { if ((mask & 1 << j) != 0) { dp[mask][i] =dp[mask ^ (1 << i)][j] + dist[j][i]; } } } } } int res = Integer.MAX_VALUE; for (int i = 1; i < n; i++) { res = dp[(1 << n) - 1][i] + dist[i][0]; } // reconstruct path int cur = (1 << n) - 1; int[] order = new int[n]; int last = 0; for (int i = n - 1; i >= 1; i--) { int bj = -1; for (int j = 1; j < n; j++) { if ((cur & 1 << j) != 0 && (bj == -1 || dp[cur][bj] + dist[bj][last] > dp[cur][j] + dist[j][last])) { bj = j; } } order[i] = bj; cur ^= 1 << bj; last = bj; } System.out.println(Arrays.toString(order)); return res; } // Usage example public static void main(String[] args) { int[][] dist = { { 0, 1, 10, 1, 10 }, { 1, 0, 10, 10, 1 }, { 10, 10, 0, 1, 1 }, { 1, 10, 1, 0, 10 }, { 10, 1, 1, 10, 0 } }; System.out.println(5 == getCycle(dist)); } } |
07.05.2012, 23:52 | |
Helpmaster
Member
Регистрация: 08.03.2016
Сообщений: 0
|
Некоторые темы по содержанию очень напоминают вашу тему Помогите с программой Помогите с программой Помогите с программой Помогите с программой на C++ |
Ads | |
Member
Регистрация: 31.10.2006
Сообщений: 40200
Записей в дневнике: 0
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Репутация: 55070
|
Метки |
java |
|
|