一、問題描述
給定 n 件物品，物品的重量為 w[i]，物品的價(jià)值為 c[i]?，F(xiàn)挑選物品放入背包中，假定背包能承受的最大重量為 V，問應(yīng)該如何選擇裝入背包中的物品，使得裝入背包中物品的總價(jià)值最大
二、解決思路
物品是不能拆分的，首先想到的是動(dòng)態(tài)規(guī)劃，將背包問題分為兩個(gè)子問題，求解子問題的最優(yōu)解。回溯法可以解決這個(gè)問題，將所有的解羅列出來，叫做解空間，然后在每個(gè)解空間上，判斷每個(gè)物品是否加入背包，每個(gè)物品相當(dāng)于一個(gè)節(jié)點(diǎn)，加入和不加入相當(dāng)于兩條路，具體是看走哪條路。
01背包.png
在向下遞歸查找最優(yōu)解的過程中，主要看兩個(gè)函數(shù)，一個(gè)是當(dāng)前路能夠走，另一個(gè)就是當(dāng)前路走下去是不是最優(yōu)解。分別叫做限界條件、減枝函數(shù)，這兩個(gè)函數(shù)的好壞影響算法的效率。
三、代碼
public class MapColoring {
public static void main(String[] args) {
//鄰接矩陣存儲(chǔ)圖 0代表相連否則不相連
int[][] adjacencyMatrix = new int[][]{
{0, 1, 1, 1, 0, 0, 0},
{1, 0, 1, 0, 1, 0, 0},
{1, 1, 0, 1, 1, 0, 0},
{1, 0, 1, 0, 1, 0, 1},
{0, 1, 1, 1, 0, 1, 1},
{0, 0, 0, 0, 1, 0, 1},
{0, 0, 0, 1, 1, 1, 0},
};
//記錄所有的結(jié)果
int[][] allResult = new int[adjacencyMatrix.length][adjacencyMatrix.length];
int[] currentValue = new int[adjacencyMatrix.length];
coloring(adjacencyMatrix, allResult, 0, currentValue, 3, 0);
for (int i = 0; i < allResult.length; i++) {
System.out.println(Arrays.toString(allResult[i]));
}
}
/**
* 地圖著色
*
* @param adjacencyMatrix 鄰接矩陣
* @param allResult 所有的結(jié)果集
* @param i 當(dāng)前點(diǎn)
*/
public static int coloring(int[][] adjacencyMatrix, int[][] allResult, int i, int[] currentValue, int color, int resultIndex) {
/**
* 判斷當(dāng)前節(jié)點(diǎn)的著色
* 循環(huán)已經(jīng)著色的點(diǎn) ,如果相連則判斷能否著色當(dāng)前顏色
* 循環(huán)顏色
*/
if (i > adjacencyMatrix.length - 1) {
//將當(dāng)前結(jié)果保存到全部結(jié)果中
for (int j = 0; j < currentValue.length; j++) {
allResult[resultIndex][j] = currentValue[j];
}
resultIndex += 1;
return resultIndex;
}
for (int j = 1; j <= color; j++) {
// 記錄當(dāng)前節(jié)點(diǎn)的顏色嘗試
if (isOk(adjacencyMatrix, j, currentValue, i)) {
// 當(dāng)前節(jié)點(diǎn)染色j
currentValue[i] = j;
//向下遞歸 如果這條路最終能走到葉子節(jié)點(diǎn)，則會(huì)加入到allResult
resultIndex = coloring(adjacencyMatrix, allResult, i + 1, currentValue, color, resultIndex);
//由于這里是for循環(huán)嘗試其他的道路，所以不用手動(dòng)回溯，下次currentValue[i] = j; 會(huì)將本次循環(huán)值覆蓋，直到達(dá)到葉子節(jié)點(diǎn)保存結(jié)果
}
}
return resultIndex;
}
/**
* 判斷當(dāng)前節(jié)點(diǎn)是否可以進(jìn)行找色
* 循環(huán)已經(jīng)作色的點(diǎn) 當(dāng)相鄰再判斷顏色是否相等
*
* @param adjacencyMatrix 鄰接矩陣
* @param colorIndex 判斷的顏色
* @param currentValue 當(dāng)前值列表
* @param i 當(dāng)前節(jié)點(diǎn)
* @return
*/
public static boolean isOk(int[][] adjacencyMatrix, int colorIndex, int[] currentValue, int i) {
for (int j = 0; j < i; j++) {
if (adjacencyMatrix[j][i] == 1) {
if (currentValue[j] == colorIndex) {
return false;
}
}
}
return true;
}
