1.0-1 背包问题
选择几件物品,装载到背包中。在不超过背包所能装载重量的前提下,如何让背包中物品的总重量最大?
(1)回溯解法
时间复杂度O(2^n)
private int maxW = Integer.MIN_VALUE; // 结果放到maxW中
/**
*
* @param items 每个物品的重量
* @param n 物品个数
* @param i 考察到哪个物品
* @param cw 当前已经装进去的物品的重量和
* @param lw 背包重量
*/
public void f(int[] items, int n, int i, int cw, int lw) {
if (i == n || cw == lw) {// cw==w表示装满了;i==n表示已经考察完所有的物品
if (cw > maxW) {
maxW = cw;
}
return;
}
f(items, n, i + 1, cw, lw);//不装
if (cw + items[i] <= lw) {
f(items, n, i + 1, cw + items[i], lw);//装进背包
}
}
(2)备忘录解法
private int maxW = Integer.MIN_VALUE; // 结果放到maxW中
private int[] weight = {2, 2, 4, 6, 3}; // 物品重量
private int n = 5; // 物品个数
private int w = 9; // 背包承受的最大重量
private boolean[][] mem = new boolean[n][w + 1];//重量可以等于w
public void f(int i, int cw) {
if (cw == w || i == n) {
if (cw > maxW) {
maxW = cw;
}
return;
}
if (mem[i][cw]) return;
mem[i][cw] = true;
f(i + 1, cw);
if (cw + weight[i] <= w) {
f(i + 1, cw + weight[i]);
}
}
(3)动态规划解法
时间复杂度: O(n*w)
public void kmpF(int[] weight, int n, int w) {
boolean[][] state = new boolean[n][w + 1];
state[0][0] = true;
if (weight[0] <= w) {
state[0][weight[0]] = true;
}
for (int i = 1; i < n; i++) {
for (int j = 0; j <= w; j++) {
if (state[i - 1][j]) {
state[i][j] = true;
}
}
for (int j = 0; j <= w - weight[i]; j++) {
if (state[i - 1][j]) {
state[i][j + weight[i]] = true;
}
}
}
for (int i = w; i >= 0; i--) {
if (state[n - 1][i]) {
System.out.println("最大重量为:" + i);
break;
}
}
}
使用一维数组降低空间消耗:
public static void kmpF2(int[] weight, int n, int w) {
boolean[] state = new boolean[w + 1];
state[0] = true;
if (weight[0] <= w) {
state[weight[0]] = true;
}
for (int i = 1; i < n; i++) {
for (int j = w - weight[i]; j >= 0; j--) {//j 需要从大到小来处理。如果我们按照 j 从小到大处理的话,会出现 for 循环重复计算的问题。
if (state[j]) {
state[j + weight[i]] = true;
}
}
}
for (int i = w; i >= 0; i--) {
if (state[i]) {
System.out.println("最大重量为:" + i);
break;
}
}
}
2.升级版0-1背包问题
对于一组不同重量、不同价值、不可分割的物品,我们选择将某些物品装入背包,在满足背包最大重量限制的前提下,背包中可装入物品的总价值最大是多少呢?
(1)回溯解法
private static int maxV = Integer.MIN_VALUE; // 结果放到maxV中
private static int[] items = {2, 2, 4, 6, 3}; // 物品的重量
private static int[] value = {3, 4, 8, 9, 6}; // 物品的价值
private static int n = 5; // 物品个数
private static int w = 9; // 背包承受的最大重量
public static void f(int i, int cw, int cv) {
if (i == n || cw == w) {
if (maxV < cv) {
maxV = cv;
}
return;
}
f(i + 1, cw, cv);
if (cw + items[i] <= w) {
f(i + 1, cw + items[i], cv + value[i]);
}
}
(2)动态规划解法
private static int maxV = Integer.MIN_VALUE; // 结果放到maxV中
private static int[] items = {2, 2, 4, 6, 3}; // 物品的重量
private static int[] value = {3, 4, 8, 9, 6}; // 物品的价值
private static int n = 5; // 物品个数
private static int w = 9; // 背包承受的最大重量
public static void dpF(int[] weight, int n, int[] value, int w) {
int[][] state = new int[n][w + 1];
for (int i = 0; i < n; i++) {
for (int j = 0; j <= w; j++) {
state[i][j] = -1;
}
}
state[0][0] = 0;
if (weight[0] <= w) {
state[0][weight[0]] = value[0];
}
for (int i = 1; i < n; i++) {
for (int j = 0; j <= w; j++) {
if (state[i - 1][j] >= 0) {
state[i][j] = state[i - 1][j];
}
}
for (int j = 0; j <= w - weight[i]; j++) {
if (state[i - 1][j] >= 0) {
int v = state[i - 1][j] + value[i];
if (v > state[i][j + weight[i]]) {
state[i][j + weight[i]] = v;
}
}
}
}
int maxVal = Integer.MIN_VALUE;
for (int j = 0; j <= w; j++) {
if (state[n - 1][j] > maxVal) {
maxVal = state[n - 1][j];
}
}
System.out.println("最大值为:" + maxVal);
}
使用一维数组降低空间消耗:
private static int maxV = Integer.MIN_VALUE; // 结果放到maxV中
private static int[] items = {2, 2, 4, 6, 3}; // 物品的重量
private static int[] value = {3, 4, 8, 9, 6}; // 物品的价值
private static int n = 5; // 物品个数
private static int w = 9; // 背包承受的最大重量
public static void dpF(int[] weight, int n, int[] value, int w) {
int[] state = new int[w + 1];
for (int j = 0; j <= w; j++) {
state[j] = -1;
}
state[0] = 0;
if (weight[0] <= w) {
state[weight[0]] = value[0];
}
for (int i = 1; i < n; i++) {
for (int j = w - weight[i]; j >= 0; j--) {
if (state[j] >= 0) {
int v = state[j] + value[i];
if (v > state[j + weight[i]]) {
state[j + weight[i]] = v;
}
}
}
}
int maxVal = Integer.MIN_VALUE;
for (int j = 0; j <= w; j++) {
if (state[j] > maxVal) {
maxVal = state[j];
}
}
System.out.println("最大值为:" + maxVal);
}
3.杨辉三角
“杨辉三角”现在对它进行一些改造:每个位置的数字可以随意填写,经过某个数字只能到达下面一层相邻的两个数字。假设你站在第一层,往下移动,我们把移动到最底层所经过的所有数字之和,定义为路径的长度。请求出从最高层移动到最底层的最短路径长度。
(1)回溯解法
public static void yanghuiTriangle(int[][] matrix, int i, int j, int currLevel, int totalLevel, int dist) {
dist = dist + matrix[i][j];//加上当前的结点才是该层的值
if (currLevel == (totalLevel - 1)) {
if (dist < minDist) {
minDist = dist;
}
return;
}
if (i + 1 < totalLevel) {
yanghuiTriangle2(matrix, i + 1, j, currLevel + 1, totalLevel, dist);
int nextLen = matrix[i + 1].length;
if (j + 1 < nextLen) {
yanghuiTriangle2(matrix, i + 1, j + 1, currLevel + 1, totalLevel, dist);
}
}
}
public static void main(String[] args) {
int[][] matrix = {{5}, {7, 8}, {2, 3, 4}, {4, 9, 6, 1}, {2, 7, 9, 4, 5}};//杨辉三角每一层的数字
yanghuiTriangle(matrix, 0, 0, 0, matrix.length, 0);
System.out.println(minDist);
}
(2)动态规划解法
状态转移方程:
f(i,j) = matrix(i,j) + min(f(i-1,j),f(i-1,j-1))
状态转移表:
括号中对应matrix中原来的值
private static void yanghuiTriangle(int[][] matrix) {
if (matrix == null) return;
int[][] state = new int[matrix.length][matrix.length];
state[0][0] = matrix[0][0];//初始化第一行
for (int i = 1; i < matrix.length; i++) {
for (int j = 0; j < matrix[i].length; j++) {
int min = Integer.MAX_VALUE;
if (j < matrix[i - 1].length) {
min = state[i - 1][j];
}
if (j - 1 >= 0) {
min = Math.min(min, state[i - 1][j - 1]);
}
state[i][j] = min + matrix[i][j];
}
}
int min = Integer.MAX_VALUE;
for (int j = 0; j < state.length - 1; j++) {
if (state[state.length - 1][j] < min) {
min = state[state.length - 1][j];
}
}
System.out.println("从顶层到底层最短路径为:" + min);
}
使用一维数组降低空间消耗:
private static void yanghuiTriangle(int[][] matrix) {
if (matrix == null) return;
int[] state = new int[matrix.length];//保存每一层最短路径
state[0] = matrix[0][0];//初始化第一行
for (int i = 1; i < matrix.length; i++) {
int min = Integer.MAX_VALUE;
for (int j = 0; j < matrix[i].length; j++) {
if (j < matrix[i - 1].length) {
min = Math.min(min, matrix[i - 1][j]);
}
if (j - 1 >= 0) {
min = Math.min(min, matrix[i - 1][j - 1]);
}
}
state[i] = state[i - 1] + min;
}
System.out.println("从顶层到底层最短路径为:" + state[matrix.length - 1]);
}
4.矩阵最短距离
假设有一个 n 乘以 n 的矩阵 w[n][n]。矩阵存储的都是正整数。棋子起始位置在左上角,终止位置在右下角。将棋子从左上角移动到右下角。每次只能向右或者向下移动一位。从左上角到右下角,会有很多不同的路径可以走。我们把每条路径经过的数字加起来看作路径的长度。那从左上角移动到右下角的最短路径长度是多少呢?
(1)回溯解法
private static int min = Integer.MAX_VALUE;
public static void minDist(int[][] w, int i, int j, int dist, int n) {
if (i == (n - 1) && j == (n - 1)) {
if (dist + w[i][j] < min) {
min = dist + w[i][j];
}
return;
}
if (i < n - 1) {
minDist(w, i + 1, j, dist + w[i][j], n);//向下走
}
if (j < n - 1) {
minDist(w, i, j + 1, dist + w[i][j], n);//向右走
}
}
(2)动态规划解法
状态转移表法:
public static void minDistDp(int[][] matrix, int n) {
int[][] state = new int[n][n];
state[0][0] = matrix[0][0];
for (int j = 1; j < n; j++) {//初始化第一行
state[0][j] = state[0][j - 1] + matrix[0][j];
}
for (int i = 1; i < n; i++) {//初始化第一列
state[i][0] = state[i - 1][0] + matrix[i][0];
}
for (int i = 1; i < n; i++) {
for (int j = 1; j < n; j++) {
state[i][j] = matrix[i][j] + Math.min(state[i - 1][j], state[i][j - 1]);
}
}
System.out.println("min val from (0,0) To (n-1,n-1):" + state[n - 1][n - 1]);
}
public static void main(String[] args) {
int n = 4;
int[][] w = {{1, 3, 5, 9}, {2, 1, 3, 4}, {5, 2, 6, 7}, {6, 8, 4, 3}};
minDistDp(w, n);
}
状态转移方程法:
状态转移方程:min_dist(i, j) = w[i][j] + min(min_dist(i, j-1), min_dist(i-1, j))
递归加“备忘录”:
private static int n = 5;
private static int[][] mem = new int[n][n];
private static int[][] matrix = {{1, 3, 5, 9}, {2, 1, 3, 4}, {5, 2, 6, 7}, {6, 8, 4, 3}};
public static int minDistDp2(int i, int j) {
if (i == 0 && j == 0) {//递归终止条件
return matrix[0][0];
}
if (mem[i][j] > 0) {
return mem[i][j];
}
int curMinUp = Integer.MAX_VALUE;
if (i - 1 >= 0) {
curMinUp = minDistDp2(i - 1, j);
}
int curMinLeft = Integer.MAX_VALUE;
if (j - 1 >= 0) {
curMinLeft = minDistDp2(i, j - 1);
}
int curMinDist = matrix[i][j] + Math.min(curMinLeft, curMinUp);
mem[i][j] = curMinDist;
return curMinDist;
}
public static void main(String[] args) {
System.out.println(minDistDp2(n - 1, n - 1));
}
5.硬币找零问题
假设我们有几种不同币值的硬币 v1,v2,……,vn(单位是元)。如果我们要支付 w 元,求最少需要多少个硬币。
比如,我们有 3 种不同的硬币,1 元、3 元、5 元,我们要支付 9 元,最少需要 3 个硬币(3 个 3 元的硬币)。
(1)回溯解法
private static int minCoin = Integer.MAX_VALUE;
public static void f(int[] money, int total, int num) {
if (total == 0) {
if (num < minCoin) {
minCoin = num;
}
return;
}
for (int m : money) {//一种硬币可以使用多次
if (total - m >= 0) {
f(money, total - m, num + 1);
}
}
}
(2)动态规划解法
public static void countMoneyMin(int[] money, int total) {
int maxLevel = total / money[0];
int[][] state = new int[maxLevel][total + 1];
for (int i = 0; i < money.length; i++) {
if (money[i] <= total) {
state[0][money[i]] = money[i];
}
}
int num = 0;
if (state[0][total] > 0) {
num = 1;
}
if (num == 0) {
for (int i = 1; i < maxLevel; i++) {
for (int j = 0; j <= total; j++) {
if (state[i - 1][j] > 0) {
for (int k : money) {
if (j + k <= total) {
state[i][j + k] = k;
}
}
}
}
if (state[i][total] > 0) {//已经找到了
num = i + 1;
break;
}
}
}
System.out.println(num);
int j = total;
for (int i = num - 1; i >= 0; i--) {
if (state[i][j] > 0) {
System.out.print("choose:" + state[i][j] + ",");
j = j - state[i][j];
}
}
}
使用一维数组优化空间复杂度:
public int getLeastCoinNumByDP(int[] coinVal, int total) {
// coinNum存放的是每个对应金额下最少硬币的最优解
int coinNum[] = new int[total + 1];
//初始化coinNum数组,硬币值数组对应的值的硬币数量都为1
for (int i = 0; i < coinVal.length; i++) {
coinNum[coinVal[i]] = 1;
}
for (int i = 1; i <= total; i++) {
if (coinNum[i] == 0) {
int minTemp = Integer.MAX_VALUE; // 获取每个i对应的最小硬币数值
for (int j = 0; j < coinVal.length; j++) {
if (i - coinVal[j] > 0) {
int v1 = coinNum[i - coinVal[j]] + 1;
if (v1 < minTemp) {
minTemp = v1;
}
}
}
coinNum[i] = minTemp;
}
}
return coinNum[total];
}
参考:
[1]40 | 初识动态规划:如何巧妙解决“双十一”购物时的凑单问题?-极客时间
[2]41 | 动态规划理论:一篇文章带你彻底搞懂最优子结构、无后效性和重复子问题-极客时间