本文共 3098 字，大约阅读时间需要 10 分钟。

动态规划算法是解决许多复杂问题的有效方法，特别是在处理有重叠子问题和最优子结构性质的问题时。动态规划的核心思想是通过分解问题，将大问题转化为多个小问题来解决，并通过记录中间结果避免重复计算，从而提高效率。

动态规划算法概述

动态规划常常适用于以下类型的问题：

背包问题

0/1背包问题是最经典的动态规划应用之一。问题描述是：给定多个物品，每个物品只能选择完全装入背包或不装入，求背包中总价值的最大值。

问题描述

• 物品重量：各不相同。
• 物品价值：各不相同。
• 背包容量：固定值。

目标是选择物品的组合，使得总价值最大，同时不超过背包容量。

思路分析

动态规划常用备忘录法解决背包问题。通过创建二维数组记录不同容量和物品组合下的最大价值。

解决问题的策略

代码实现

private int[][] knapsack(int[] weight, int[] value, int capacity) {    int num = weight.length;    int[][] res = new int[num + 1][capacity + 1];    int[][] path = new int[num + 1][capacity + 1];        for (int i = 0; i < res.length; i++) {        res[i][0] = 0;    }    for (int i = 0; i < res[0].length; i++) {        res[0][i] = 0;    }        for (int i = 1; i < res.length; i++) {        for (int j = 1; j < res[i].length; j++) {            if (weight[i - 1] > j) {                res[i][j] = res[i - 1][j];            } else {                if (res[i - 1][j] < value[i - 1] + res[i - 1][j - weight[i - 1]]) {                    res[i][j] = value[i - 1] + res[i - 1][j - weight[i - 1]];                    path[i][j] = 1;                } else {                    res[i][j] = res[i - 1][j];                }            }        }    }    int i = path.length - 1;    int j = path[0].length - 1;    while (i > 0 && j > 0) {        if (path[i][j] == 1) {            System.out.println("第" + i + "个物品被装入背包");            j -= weight[i - 1];        }        i--;    }    return res;}

代码测试

@Testpublic void test() {    int[] weight = {1, 4, 3};    int[] value = {1500, 3000, 2000};    int capacity = 4;    int[][] knapsack = knapsack(weight, value, capacity);    for (int[] each : knapsack) {        System.out.println(Arrays.toString(each));    }}

优化后的代码

为了更清楚地了解装入物品，可以增加路径数组记录物品装入情况。

private int[][] knapsack(int[] weight, int[] value, int capacity) {    int num = weight.length;    int[][] res = new int[num + 1][capacity + 1];    int[][] path = new int[num + 1][capacity + 1];        for (int i = 0; i < res.length; i++) {        res[i][0] = 0;    }    for (int i = 0; i < res[0].length; i++) {        res[0][i] = 0;    }        for (int i = 1; i < res.length; i++) {        for (int j = 1; j < res[i].length; j++) {            if (weight[i - 1] > j) {                res[i][j] = res[i - 1][j];            } else {                if (res[i - 1][j] < value[i - 1] + res[i - 1][j - weight[i - 1]]) {                    res[i][j] = value[i - 1] + res[i - 1][j - weight[i - 1]];                    path[i][j] = 1;                } else {                    res[i][j] = res[i - 1][j];                }            }        }    }    int i = path.length - 1;    int j = path[0].length - 1;    while (i > 0 && j > 0) {        if (path[i][j] == 1) {            System.out.println("第" + i + "个物品被装入背包");            j -= weight[i - 1];        }        i--;    }    return res;}

测试结果

运行结果显示了二维数组res，其中res[i][j]表示装入i个物品时，背包容量为j时的最大价值。路径数组path记录了每个状态是否放入物品，帮助理解背包中装入了哪些物品。

通过动态规划算法，我们可以高效地解决背包问题，找到最大价值的装入组合。

转载地址：http://jxgh.baihongyu.com/