一、问题描述
给定 n 件物品，物品的重量为 w[i]，物品的价值为 c[i]。现挑选物品放入背包中，假定背包能承受的最大重量为 V，问应该如何选择装入背包中的物品，使得装入背包中物品的总价值最大
二、解决思路
物品是不能拆分的，首先想到的是动态规划，将背包问题分为两个子问题，求解子问题的最优解。回溯法可以解决这个问题，将所有的解罗列出来，叫做解空间，然后在每个解空间上，判断每个物品是否加入背包，每个物品相当于一个节点，加入和不加入相当于两条路，具体是看走哪条路。
01背包.png
在向下递归查找最优解的过程中，主要看两个函数，一个是当前路能够走，另一个就是当前路走下去是不是最优解。分别叫做限界条件、减枝函数，这两个函数的好坏影响算法的效率。
三、代码
public class MapColoring {
public static void main(String[] args) {
//邻接矩阵存储图 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},
};
//记录所有的结果
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 所有的结果集
* @param i 当前点
*/
public static int coloring(int[][] adjacencyMatrix, int[][] allResult, int i, int[] currentValue, int color, int resultIndex) {
/**
* 判断当前节点的着色
* 循环已经着色的点 ,如果相连则判断能否着色当前颜色
* 循环颜色
*/
if (i > adjacencyMatrix.length - 1) {
//将当前结果保存到全部结果中
for (int j = 0; j < currentValue.length; j++) {
allResult[resultIndex][j] = currentValue[j];
}
resultIndex += 1;
return resultIndex;
}
for (int j = 1; j <= color; j++) {
// 记录当前节点的颜色尝试
if (isOk(adjacencyMatrix, j, currentValue, i)) {
// 当前节点染色j
currentValue[i] = j;
//向下递归 如果这条路最终能走到叶子节点，则会加入到allResult
resultIndex = coloring(adjacencyMatrix, allResult, i + 1, currentValue, color, resultIndex);
//由于这里是for循环尝试其他的道路，所以不用手动回溯，下次currentValue[i] = j; 会将本次循环值覆盖，直到达到叶子节点保存结果
}
}
return resultIndex;
}
/**
* 判断当前节点是否可以进行找色
* 循环已经作色的点 当相邻再判断颜色是否相等
*
* @param adjacencyMatrix 邻接矩阵
* @param colorIndex 判断的颜色
* @param currentValue 当前值列表
* @param i 当前节点
* @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;
}
