前言

动态规划是一种解决复杂问题的方法，关键思想是将大问题分解为一组更简单的子问题，只解决每个子问题一次，并使用基于内存的数据结构存储解决方案。每个子问题解决方案都以某种方式被索引。通常使用输入参数的值，用于查找。所以，当出现相同的子问题时，无需重新计算解决方案，而是查找以前计算的解决方案，从而节省计算时间，这种存储子问题解决方案的思想就成为动态规划。

在一张纸上写下“1 1 1 1 1 1 1 1 = ？

回答："八！"

在左边在写下另一个“1 ”，等于多少？

回答："九！"

你怎么算的这么快呢？

回答："你刚刚只是又加了一"。

所以你不需要重新计算，因为你记得有八个！动态编程只是一种花哨的方式来表达记住一些东西以节省时间

动态规划经典问题：0-1背包问题

现在要出去旅游，整理出来一些物品，每个物品有两个属性，必要性和重量，书包的承重有限，要求是在满足书包承重的基础上，尽可能的装最需要的东西。每个物品只能装一个。

代码示例：

输入：
 
必要性 = [ 20, 5, 10, 40, 15, 25 ]\
重量 = [ 1, 2, 3, 8, 7, 4 ]\
int W = 10（W为书包的承重极限）

输出：背包装的必要性为 60
 
必要性 = 20   40 = 60
重量= 1   8 = 9 < W

递归

使用递归的思想来解决这个问题。 将当前的物品包含在背包中，并且福使用背包容量减少的剩余物品。如果容量变为负数，就不返回，或者返回负无穷。

最后，返回我们通过包含或排除当前项目得到的最大值。递归的基本情况是没有剩余物品，或者容量变为 0。

Java示例代码：

class Main
{
    public static int knapsack(int[] v, int[] w, int n, int W)
    {
        if (W < 0) {
            return Integer.MIN_VALUE;
        }
 
        // base case: 没有剩余项目或容量变为0
        if (n < 0 || W == 0) {
            return 0;
        }
 
        // Case 1. 将当前物品“v[n]”放在背包中，并重复使用
        // 剩余物品'n-1'容量减少'W-W[n]`
 
        int include = v[n]   knapsack(v, w, n - 1, W - w[n]);
 
        // Case 2. 从背包中排除当前物品'v[n]'，并重复使用
        // 剩余项目'n-1`
 
        int exclude = knapsack(v, w, n - 1, W);
 
        // 返回通过包含或排除当前项得到的最大值
        return Integer.max(include, exclude);
    }
 
    public static void main(String[] args)
    {
        // 输入的值，v：必要性，w：重量
        int[] v = { 20, 5, 10, 40, 15, 25 };
        int[] w = { 1, 2, 3, 8, 7, 4 };
 
        // 背包容量
        int W = 10;
 
        System.out.println("背包必要值为 "  
                knapsack(v, w, v.length - 1, W));
    }
}

输出：
背包必要值为60

上述解决方案的时间复杂度是指数级的，并且在调用堆栈中占据空间。

上述解具有最优子结构，即可以从其子问题的最优解有效地构造最优解。它也有重叠的子问题，即问题可以分解成子问题，每个子问题重复几次。为了重用子问题解决方案，我们可以使用动态规划，其中子问题解决方案被存储而不是一遍一遍的计算。

动态规划（自顶向下）

示例：

class Main
{
    public static int knapsack(int[] v, int[] w, int n, int W)
    {
        if (W < 0) {
            return Integer.MIN_VALUE;
        }
 
        // base case: 没有剩余项目或容量变为0
        if (n < 0 || W == 0) {
            return 0;
        }
 
        // Case 1. 将当前物品“v[n]”放在背包中，并重复使用
        // 剩余物品'n-1'容量减少'W-W[n]`
        int include = v[n]   knapsack(v, w, n - 1, W - w[n]);
 
        // Case 2. 从背包中排除当前物品'v[n]'，并重复使用
        // 剩余项目`n-1`
 
        int exclude = knapsack(v, w, n - 1, W);
 
        // 返回通过包含或排除当前项得到的最大值
        return Integer.max(include, exclude);
    }
 
    public static void main(String[] args)
    {
        // 输入的值，v：必要性，w：重量
        int[] v = { 20, 5, 10, 40, 15, 25 };
        int[] w = { 1, 2, 3, 8, 7, 4 };
 
        // 背包容量
        int W = 10;
 
        System.out.println("背包必要值为 "  
                knapsack(v, w, v.length - 1, W));
    }
}

输出：
背包必要值为60

上述自顶向下解决方案的时间复杂度为O(nW)，需要O(nW)额外空间，其中n是输入中的物品总数，W是背包的容量。

我们也可以采用自下而上的方式解决这个问题。在自下而上的方法中，我们首先解决较小的子问题，然后从中解决较大的子问题。以下自下而上的方法T[i][j]为每个1 <= i <= n和计算 ，这是在权重小于或等于并使用最多第一项的项目时0 <= j <= W可以获得的最大值。使用较小值且已计算的值。。

动态规划（自下而上）

class Main
{
    public static int knapsack(int[] v, int[] w, int W)
    {
        // `T[i][j]`存储背包重量的最大值
        // 小于等于'j'，仅考虑前'i'项。
        int[][] T = new int[v.length   1][W   1];
 
        for (int i = 1; i <= v.length; i  )
        {
            // 考虑从0到最大容量W的所有权重
            for (int j = 0; j <= W; j  )
            {
                // 如果'j-w[i-1]'为负，则不包括第i个元素
                if (w[i-1] > j) {
                    T[i][j] = T[i-1][j];
                }
                else {
                    // 通过排除或包含找到我们得到的最大值
                    // 第i项
                    T[i][j] = Integer.max(T[i-1][j], T[i-1][j-w[i-1]]   v[i-1]);
                }
            }
        }
 
        // 返回最大的值（必要性）
        return T[v.length][W];
    }
 
    public static void main(String[] args)
    {
        // 输入的值，v：必要性，w：重量
        int[] v = { 20, 5, 10, 40, 15, 25 };
        int[] w = { 1, 2, 3, 8, 7, 4 };
 
        // 背包容量
        int W = 10;
 
        System.out.println("背包必要值为 "   knapsack(v, w, W));
    }
}

输出：
背包必要值为60

上述自下而上解决方案的时间复杂度为O(nW)，需要O(nW)额外空间，其中n是输入中的物品总数，W是背包的容量。

本文出至：学新通技术网