乐趣区

关于算法:你真的懂01背包问题吗01背包的这几问你能答出来吗

jiezi

你真的懂 01 背包问题吗？01 背包的这几问你能答出来吗？

对于 01 背包的几个问题

  • 背包问题的动静转移方程是怎么来的？
  • 你能解释背包问题的两个 for 循环的意义嘛？
  • 为什么须要两个 for 循环，一个循环行不行？
  • 01 背包问题的 for 循环肯定要从 0 开始吗？
  • 01 背包滚动数组的优化原理是什么？
  • 01 背包只用不必二维数组只用一位数组的根据是什么？

这些问题在浏览完本文之后你将会失去答案！

01 背包问题介绍

有 $N$ 件物品和一个容量是 $V$ 的背包。每件物品只能应用 一次。第 $i$ 件物品的体积是 $v_i$，价值是 $w_i$。求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。

比方上面的 4 个物品，背包可能接受的最大分量为 5，咱们应该如何抉择，使得咱们取得的总价值最大：

物品 分量 价值
A 1 2
B 2 4
C 3 4
D 4 5

这个问题还是比较简单，咱们间接看就晓得抉择物品 B 和物品 C 失去的价值最大。那么咱们如何设计一个算法去实现这个问题呢？首先对于每一个物品都有两种状况，抉择和不抉择，咱们须要抉择两种状况当中可能获取最大价值的那种状况。

01 背包问题动静转移方程

首先我么先要确定一个信息就是没件物品只有一件，选完就没有了。如果咱们的背包当中还有残余容量能够放下某个物品，那么对于这个物品咱们就有两种抉择：选 或者 不选。

咱们定义数组 dp[i][j]，其含意是对于前i 件物品，在咱们的背包容量为 j 的状况下咱们可能取得的最大的收益，如果咱们有 N 件物品，背包容量为 V，那么咱们可能取得的最大价值为dp[N][V]，因为他示意的是对于前N 个物品，在背包容量为 V 的状况下咱们可能获取到的最大的价值。咱们能够失去上面的公式：

$$
dp[i][j]=max(dp[i – 1][j – v[i]] + w[i], dp[i – 1][j])，如果背包的容量大于等于物品 i 占的体积
$$

$$
dp[i][j]=dp[i – 1][j]，如果背包的容量小于物品 i 占的体积
$$

  • 第一种状况（背包容量大于等于第 i 件物品的体积 v[i] 时）：

    • 在这种状况下咱们对于第 i 件物品有两种抉择，一种是将其放入背包当中，另外一种就是不选他，那么咱们就能够应用容量为 j 的背包在前 i-1 件物品进行抉择。
    • 如果咱们选第 i 件物品，那么咱们背包剩下的容量就为 j - v[i]，咱们还能抉择的物品就是前i - 1 个物品，这个状况下可能取得的最大的收益为 $dp[i – 1][j – v[i]]$，再加上咱们抉择的第 i 件物品的价值，咱们抉择第 i 件物品可能取得的总收益为dp[i - 1][j - v[i]] + w[i]。
    • 如果咱们不抉择第 i 件物品，那么咱们背包残余容量依然为j，而且咱们只能从前i - 1 个商品当中进行抉择，那么咱们最大的收益就为dp[i - 1][j]。

  • 第二种状况（背包容量小于第 i 件物品的体积 v[i] 时）：

    • 这种状况下咱们只可能抉择前 i - 1 个商品，因而咱们可能获取的最大收益为dp[i - 1][j]。

01 背包数据依赖问题剖析

在上文当中咱们曾经剖析进去了咱们的动静转移方程：

$$
dp[i][j]=max(dp[i – 1][j – v[i]] + w[i], dp[i – 1][j])，如果背包的容量大于等于物品 i 占的体积
$$

$$
dp[i][j]=dp[i – 1][j]，如果背包的容量小于物品 i 占的体积
$$

依据下面两个公式剖析，咱们晓得要想解出 dp[i][j] 的值，咱们首先须要晓得 dp[i - 1][j - v[i]] 的值和 dp[i - 1][j] 的值，他们之间的依赖关系如下图所示：

基于下面的数据依赖关系，咱们晓得咱们如果想求 dp[N][V] 的值，首先要求出 dp 数组第 N - 1 行的所有的值，因为 dp[N][V] 依赖 dp[N - 1][V]，而且可能依赖dp[N - 1][i] 的值（i大于等于 0，小于V），而dp[N - 1][V] 又依赖dp[N - 2][]V……

依据下面的剖析过程，如果咱们想计算出 dp[N][V] 的后果，那就须要从第 1 行开始往后计算，始终算到第 N 行，因而咱们能够写出上面的代码：

Java版本：

import java.util.Scanner;

public class Main {public static int backpack(int[] w, int[] v, int N, int V) {int[][] dp = new int[N + 1][V + 1];
    // 初始化
    for (int i = v[1]; i <= V; ++i) {dp[1][i] = w[1];
    }
    // 第一行曾经初始化 从第二行开始
    for (int i = 2; i <= N; ++i) {for (int j = 0; j <= V; ++j) {if (j >= v[i])
          dp[i][j] = Math.max(dp[i - 1][j - v[i]] + w[i], dp[i - 1][j]);
        else
          dp[i][j] = dp[i - 1][j];
      }
    }
    return dp[N][V];
  }

  public static void main(String[] args) {Scanner scanner = new Scanner(System.in);
    int N = scanner.nextInt();
    int V = scanner.nextInt();
    int[] w = new int[N + 1];
    int[] v = new int[N + 1];
    for (int i = 1; i <= N; i++) {v[i] = scanner.nextInt();
      w[i] = scanner.nextInt();}
    System.out.println(backpack(w, v, N, V));
  }
}

C++版本：

#include <iostream>
using namespace std;

#define L 20000
int w[L]; // 物品价值
int v[L]; // 物品体积
int dp[L][L];

int N; // 物品数量
int V; // 背包的体积

int backpack() {

    // 初始化
    for (int i = v[1]; i <= V; ++i) {dp[1][i] = w[1];
    }
    // 第一行曾经初始化 从第二行开始
    for (int i = 2; i <= N; ++i) {for (int j = 0; j <= V; ++j) {if (j >= v[i])
                dp[i][j] = max(dp[i - 1][j - v[i]] + w[i], dp[i - 1][j]);
            else
                dp[i][j] = dp[i - 1][j];
        }
    }
    return dp[N][V];
}

int main() {
    cin >> N >> V;
    for (int i = 1; i <= N; ++i) {cin >> v[i] >> w[i];
    }
    cout << backpack();
    return 0;
}

从上图看咱们在计算第 i 的数据的时候咱们只依赖第 i - 1 行，咱们在第 i 行从后往前遍历并不会毁坏动静转移公式的要求。

因而上面的代码也是正确的：

public static int backpack(int[] w, int[] v, int N, int V) {int[][] dp = new int[N + 1][V + 1];
    // 初始化
    for (int i = v[1]; i <= V; ++i) {dp[1][i] = w[1];
    }
    // 第一行曾经初始化 从第二行开始
    for (int i = 2; i <= N; ++i) {
        // 这里是从开端到 0
        // 后面是从 0 遍历到开端
        for (int j = V; j >= 0; --j) {if (j >= v[i])
                dp[i][j] = Math.max(dp[i - 1][j - v[i]] + w[i], dp[i - 1][j]);
            else
                dp[i][j] = dp[i - 1][j];
        }
    }
    return dp[N][V];
}

01 背包问题优化——滚动数组

咱们在解决背包问的时候咱们是开拓了一个二维数组 dp，那么咱们能不能想斐波拉契数列那样升高算法的空间复杂度呢？咱们曾经很分明了咱们在计算dp 数据的时候进行计算的时候只应用了两行数据，那么咱们只须要申请两行的空间即可，不须要申请那么大的数组空间，计算的时候重复在两行数据当中交替计算既可。比如说咱们曾经计算好第一行的数据了（初始化），那么咱们能够依据第一行失去的后果失去第二行，而后依据第二行，将计算的结后果从新存储到第一行，如此交替重复，像这种办法叫做 滚动数组。

上面的代码当中 dp 数组是从第 0 行开始应用的，后面的代码是从第一行开始的。

import java.util.Scanner;

public class Main {public static int backpack(int[] v, int[] w, int V) {
      int N = w.length;
      int[][] dp = new int[2][V + 1];
      for (int i = v[0]; i < V; ++i) {dp[0][i] = w[0];
      }
      for (int i = 1; i < N; ++i) {for (int j = V; j >= 0; --j) {if (j >= v[i])
            dp[i % 2][j] = Math.max(dp[(i - 1) % 2][j],
                dp[(i - 1) % 2][j - v[i]] + w[i]);
          else
            dp[i % 2][j] = dp[(i - 1) % 2][j];
        }
      }
      return dp[(N - 1) % 2][V];
  }


  public static void main(String[] args) {Scanner scanner = new Scanner(System.in);
    int N = scanner.nextInt();
    int V = scanner.nextInt();
    int[] w = new int[N];
    int[] v = new int[N];
    for (int i = 0; i < N; i++) {v[i] = scanner.nextInt();
      w[i] = scanner.nextInt();}
    System.out.println(backpack(v, w, V));
  }
}

背包空间再优化——单行数组和它的遍历程序问题

咱们还能持续压缩空间吗🤣？咱们在进行空间问题的优化的时候只有不毁坏动静转移公式，只须要咱们进行的优化可能满足 dp[i][j] 的计算在它所依赖的数据之后计算即可。

import java.util.Scanner;

public class Main {public static int backpack(int[] v, int[] w, int V) {
    int N = w.length;
    int[] dp = new int[V + 1];
    for (int i = v[0]; i < V; ++i) {dp[i] = w[0];
    }
    for (int i = 1; i < N; ++i) {for (int j = V; j >= v[i]; --j) {dp[j] = Math.max(dp[j - v[i]] + w[i], dp[j]);
      }
    }
    return dp[V];
  }

  public static void main(String[] args) {Scanner scanner = new Scanner(System.in);
    int N = scanner.nextInt();
    int V = scanner.nextInt();
    int[] w = new int[N];
    int[] v = new int[N];
    for (int i = 0; i < N; i++) {v[i] = scanner.nextInt();
      w[i] = scanner.nextInt();}
    System.out.println(backpack(v, w, V));
  }
}

咱们当初来好好剖析一下下面的代码：

  • 依据动静转移公式 dp[i][j] = max(dp[i - 1][j - v[i]] + w[i], dp[i - 1][j]) 咱们晓得，第 i 行的第 j 个数据只依赖第 i - 1 行的前 j 个数据，跟第 j 个数据之后的数据没有关系。因而咱们在应用一维数组的时候能够从后往前计算（且只能从后往前计算，如果从前往后计算会毁坏动静转移公式，因为第 j 个数据跟他后面的数据有依赖关系，跟他前面的数据没有依赖关系）就可能满足咱们的动静转移公式。
  • 如果咱们从在应用单行数组的时候从前往后计算，那么会使得一维数据后面局部数据的状态从 i - 1 行的状态变成第 i 行的状态，像上面这样。

然而一维数组当中后局部的数据还是 i - 1 行的状态，当咱们去更新他们的时候他们依赖后面局部数据的 i - 1 行的状态，然而他们曾经更新到第 i 的状态了，因而毁坏了动静布局的转移方程，然而如果咱们从后往前进行遍历那么后面的状态始终是第 i - 1 行的状态，因而没有毁坏动静布局的转移方程，因而咱们须要从后往前遍历。

问题答案

如果你曾经看懂下面所议论到的内容的话，对于后面的几个问题置信你曾经有了答案。下面那些问题最终波及到的就是 01 背包问题的动静转移方程了，咱们在写代码的时候肯定不能毁坏动静转移方程，也就是要满足动静转移方程的依赖关系，即第 i 行的第 j 个数据只依赖第 i - 1 行的前 j 个数据，跟第 j 个数据之后的数据没有关系。

  • 背包问题的两个 for 循环的意义：

    • 因为咱们须要解出 dp 数组当中第 N 行第 V 列的数据，所以咱们须要解出二维数组当中所有的数据，因而咱们须要进行二维数组的遍历，进行一维遍历不行。

  • 01 背包问题的 for 循环肯定要从 0 开始吗？

    • 不肯定，咱们只须要满足动静转移方程的数据依赖要求就行，不论是从返回后还是从后往前咱们在应用二维 dp 数组的遍历的时候都能够满足数据依赖的要求。然而咱们如果应用一维数组的时候就肯定要从后往前遍历，因为如果从前往后遍历，第 i 行状态会笼罩第 i - 1 行的状态，而数组前面的数据须要 i - 1 行状态的数据，而它有被笼罩了因而不行。
  • 其余问题的答案在浏览完本文之后置信你心里曾经很分明了！！！

动静布局为什么叫动静布局

首先咱们须要明确什么是 布局 所谓的 布局 就是寻找最优值的过程，比如说咱们在旅行的时候做布局就是为了又更好旅行体验，而咱们在做算法题的时候须要找到最好的后果，比方在背包问题当中咱们要找到价值最大的一种抉择，这也是一种布局，那为什么是动静的呢？所谓动静就是咱们在寻找最优值的过程当中，抉择是变动的。比如说对于背包问题的公式 dp[i][j] = max(dp[i - 1][j - v[i] + w[i], dp[i - 1][j]) 咱们在计算出后果之前并不知道那种抉择好，因为咱们要抉择两者两头值较大的哪个抉择，这就是动静抉择的过程！所以动静布局被称作动静布局！

总结

本篇文章次要带大家从 0 开始分析 01 背包问题，次要分享一些根本但常常被疏忽的问题，比方二重循环是如何被写进去的，for 循环的程序问题，数组空间优化问题的原理，用一维数组解决 01 背包问题！心愿大家有所播种，我是 LeHung，咱们下期再见！！！

更多精彩内容合集可拜访我的项目：https://github.com/Chang-LeHu…

关注公众号：一无是处的钻研僧，理解更多计算机（Java、Python、计算机系统根底、算法与数据结构）常识。

退出移动版