关于01背包问题你该了解这些！附背包九讲获取方式及相关讲解

关于01背包问题你该了解这些！附背包九讲获取方式及相关讲解

关于01个背包问题，您应该知道这些！

本周，我们正式开始解释背包问题！

当然，有关背包问题的经典信息是：背包上的九次讲座。在官方帐户“代码Sutra记录”的背景下回复：您可以通过获得背包九讲的九个讲座来获得背包九讲的PDF。

但老实说，背包的九座讲座确实对不太友好，而且它们似乎有些困难，它们都是伪编码，很难理解。

对于采访，实际上可以掌握01背包和完整的背包。最多可以，您可以获得多个背包。

如果您无法分辨这些类型的背包之间的区别，我在这里绘制一张图片，如下：

416.细分和子集1

至于背包的九次讲座中的其他背包，我在采访中几乎没有问他们。它们都处于竞争水平，并且毫无疑问，关于多个背包，银行还告诉我们，01个背包和完整的背包就足够了。

完整的背包也是一个01背包，它略有变化，即，完整背包中的项目数量是无限的。

因此，背包问题的理论基础是01背包的首要任务，您必须彻底理解它！

纯01背包没有问题，它们的应用是01背包的问题，​​这意味着它们需要将其转换为01个背包问题。

因此，我首先通过纯01背包问题解释01背包的原理。稍后我解释问题时，重点是如何将其转换为01背包问题。

一些录音机可能以前能够巧妙地编写背包，但是只要您仔细阅读本文，我相信您将获得意外的结果！

01背包

有n个项目和背包最多可以带有W的重量。第三项的权重为[i]，所获得的值是值[i]。每个项目只能使用一次，并找出将哪些项目放入背包中，并且项目的总价值最大。

动态计划 - 背包问题

这是一个标准的背包问题，因此，当他们看到这一点时，许多学生会自然会想到背包，甚至不知道如何解决暴力问题。

实际上，这是因为我没有从自下而上考虑，但是我曾经想到背包。那么解决暴力的解决方案应该是什么？

每个项目实际上只有两个状态，要么取用或不使用，因此您可以使用回溯方法来搜索所有情况，因此时间复杂性是，n在这里代表项目数量。

因此，解决暴力的解决方案是指数的时间复杂性。然后需要动态编程解决方案来优化！

在以下解释中，我将举一个例子：

背包的最大重量为4。

项目是：

重量值

项目0

15

项目1

20

项目2

30

背包可以携带的项目的最大值是多少？

以下说明和数字出现在图中，都是一个例子。

2D DP数组01背包

仍在移动五部分分析。

确定DP数组和下标的含义

对于背包问题，有一种编写它的方法，即使用二维数组，即DP [i] [j]意味着从带有下标[0-i]的项目中任意将其放入具有J的背包中。总价值的最大总和为。

如果您仅查看此二维阵列的定义，那么您一定会感到有些困惑。看以下图：

动态编程 - 背包问题1

永远记住此DP数组的含义。以下步骤围绕此DP数组的含义。如果您感到困惑，请查看我的代表和J所代表的代表。

确定递归公式

让我们回顾一下DP [i] [J]的含义：从带有下标[0-i]的项目中采取任何方式，将其放入j的背包中。总值的最大总和是多少。

然后可以有两个指示来推断DP [i] [J]，

因此，递归公式：dp [i] [j] = max（dp [i -1] [j]，dp [i -1] [j - [i]] + value [i]）;

如何初始化DP数组

关于初始化，它必须与DP数组的定义匹配，否则使用递归公式时，它将变得越来越混乱。

首先，从dp [i] [j]的定义开始，如果背包容量j为0，即dp [i] [0]，无论选择哪个项目，背包的总价值都必须为0。如图所示：

动态编程 - 背包问题2

看其他情况。

状态传输方程dp [i] [j] = max（dp [i -1] [j]，dp [i -1] [j - [i]] + value [i]）;可以看出，我是从I-1派生的，因此当我是0时，必须初始化它。

dp [0] [j]，也就是说，当我是0时，在用数字0存储项目时，可以通过每个容量的背包存储的最大值。

那么很明显，当j <[0]，dp [0] [j]为0时，因为背包容量小于编号为0的项目。

当j> = [0]时，dp [0] [j]应该是值[0]，因为背包容量足以放置数字0项目。

该代码的初始化如下：

for (int j = 0 ; j < weight[0]; j++) {  // 当然这一步，如果把dp数组预先初始化为0了，这一步就可以省略，但很多同学应该没有想清楚这一点。
    dp[0][j] = 0;
}
// 正序遍历
for (int j = weight[0]; j <= bagweight; j++) {
    dp[0][j] = value[0];
}

目前，DP数组初始化情况如图所示：

动态编程 - 背包问题7

DP [0] [J]和DP [i] [0]均已初始化，因此必须初始化多少其他下标？

实际上，来自递归公式：dp [i] [j] = max（dp [i -1] [j]，dp [i -1] [j - [i]] + value [i]）;可以看出，dp [i] [j]是从左上值派生的，所以为什么其他下标的初始值还可以，因为它们会被覆盖。

初始-1​​，初始-2，初始100，都可以！

但这只是DP阵列在开始时统一到0，这更方便。

如图所示：

动态编程 - 背包问题10

最终的初始化代码如下：

// 初始化 dp
vector> dp(weight.size(), vector(bagweight + 1, 0));
for (int j = weight[0]; j <= bagweight; j++) {
    dp[0][j] = value[0];
}

它花了很多努力来解释如何初始化它。我相信许多学生通常会根据自己的感受初始化DP阵列，但有时他们会觉得这是不可靠的。

确定遍历顺序

在下图中，可以看出有两个遍历维度：项目和背包重量

动态编程 - 背包问题3

因此，问题是，我应该先穿越项目还是背包重量？

实际上，一切都可能！呢但是首先通过项目迭代以更好地理解。

然后，我将代码首先在项目上迭代，然后在背包的重量上迭代。

// weight数组的大小 就是物品个数
for(int i = 1; i < weight.size(); i++) { // 遍历物品
    for(int j = 0; j <= bagweight; j++) { // 遍历背包容量
        if (j < weight[i]) dp[i][j] = dp[i - 1][j];
        else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

    }
}

可以先浏览背包，然后再通过项目！ （请注意我在这里使用的二维DP阵列）

例如：

// weight数组的大小 就是物品个数
for(int j = 0; j <= bagweight; j++) { // 遍历背包容量
    for(int i = 1; i < weight.size(); i++) { // 遍历物品
        if (j < weight[i]) dp[i][j] = dp[i - 1][j];
        else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
    }
}

为什么可能？

了解递归的性质和递归方向。

dp [i] [j] = max（dp [i -1] [j]，dp [i -1] [j - [i]] + value [i]）;从递归公式可以看出，dp [i] [j]源自dp [i -1] [j]和dp [i -1] [j - [i]]。

DP [i -1] [J]和DP [i -1] [J- [i]]都位于DP [i] [J]的左上角（包括向上方向）。然后，首先遍历项目然后穿越背包的过程如图所示：

动态编程 - 背包问题5

让我们看看首先穿越背包，然后穿越项目，如图所示：

动态编程 - 背包问题6

如您所见，尽管两个循环的顺序是不同的，但DP [i] [J]所需的数据位于左上角，这完全不会影响DP [i] [J]公式的推导！

但是，更好地理解了首先穿越项目然后穿越背包的顺序。

实际上，在背包问题中，两个循环的序列非常特别，并且理解遍历的顺序实际上比理解派生公式要困难得多。

推论DP阵列与示例

让我们看一下相应的DP数组值，如图所示：

动态编程 - 背包问题4

最终结果是DP [2] [4]。

建议您此时在纸上推断出它，以查看DP数组中的每个值是否是这样的。

做动态编程问题的最佳过程是在纸上举例说明相应的DP数组的值，然后手动编写代码！

许多学生做DP问题并遇到各种问题。然后他们根据自己的感受来改变它们。无论他们如何改变，他们是错误的，或者犯了错误。

最主要的是我没有推断DP阵列的演化过程。如果我理解派生词，即使编写的代码存在问题，只需打印出DP数组并将差异与我得出的差异进行比较，您很快就会发现问题。

完成C ++测试代码

void test_2_wei_bag_problem1() {
    vector<int> weight = {1, 3, 4};
    vector<int> value = {15, 20, 30};
    int bagweight = 4;

    // 二维数组
    vector<vector<int>> dp(weight.size(), vector<int>(bagweight + 1, 0));

    // 初始化
    for (int j = weight[0]; j <= bagweight; j++) {
        dp[0][j] = value[0];
    }

    // weight数组的大小 就是物品个数
    for(int i = 1; i < weight.size(); i++) { // 遍历物品
        for(int j = 0; j <= bagweight; j++) { // 遍历背包容量
            if (j < weight[i]) dp[i][j] = dp[i - 1][j];
            else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

        }
    }

    cout << dp[weight.size() - 1][bagweight] << endl;
}

int main() {
    test_2_wei_bag_problem1();
}

总结

谈论了很多之后，我刚刚完成了二维DP的01背包。在这里，您实际上可以发现最简单的是推导公式。我想我会在阅读它后将其写下来，但是困难在于如何初始化和穿越它。

一些学生可能不会注意到初始化和遍历顺序的重要性。稍后我们进行背包采访问题时，每个人都会感觉到。

下一篇文章仍然是理论基础。让我们谈谈一维DP数组实现的01背包（滚动阵列）。分析IT和二维之间的差异，以及初始化和遍历顺序的差异。敬请关注！

其他语言的Java版本

    public static void main(string[] args) {
        int[] weight = {1, 3, 4};
        int[] value = {15, 20, 30};
        int bagsize = 4;
        testweightbagproblem(weight, value, bagsize);
    }

    public static void testweightbagproblem(int[] weight, int[] value, int bagsize){
        int wlen = weight.length, value0 = 0;
        //定义dp数组：dp[i][j]表示背包容量为j时，前i个物品能获得的最大价值
        int[][] dp = new int[wlen + 1][bagsize + 1];
        //初始化：背包容量为0时，能获得的价值都为0
        for (int i = 0; i <= wlen; i++){
            dp[i][0] = value0;
        }
        //遍历顺序：先遍历物品，再遍历背包容量
        for (int i = 1; i <= wlen; i++){
            for (int j = 1; j <= bagsize; j++){
                if (j < weight[i - 1]){
                    dp[i][j] = dp[i - 1][j];
                }else{
                    dp[i][j] = math.max(dp[i - 1][j], dp[i - 1][j - weight[i - 1]] + value[i - 1]);
                }
            }
        }
        //打印dp数组
        for (int i = 0; i <= wlen; i++){
            for (int j = 0; j <= bagsize; j++){
                system.out.print(dp[i][j] + " ");
            }
            system.out.print("\n");
        }
    }

def test_2_wei_bag_problem1(bag_size, weight, value) -> int:
 rows, cols = len(weight), bag_size + 1
 dp = [[0 for _ in range(cols)] for _ in range(rows)]

 # 初始化dp数组.
 for i in range(rows):
  dp[i][0] = 0
 first_item_weight, first_item_value = weight[0], value[0]
 for j in range(1, cols):
  if first_item_weight <= j:
   dp[0][j] = first_item_value

 # 更新dp数组: 先遍历物品, 再遍历背包.
 for i in range(1, len(weight)):
  cur_weight, cur_val = weight[i], value[i]
  for j in range(1, cols):
   if cur_weight > j: # 说明背包装不下当前物品.
    dp[i][j] = dp[i - 1][j] # 所以不装当前物品.
   else:
    # 定义dp数组: dp[i][j] 前i个物品里，放进容量为j的背包，价值总和最大是多少。
    dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - cur_weight]+ cur_val)

 print(dp)


if __name__ == "__main__":
 bag_size = 4
 weight = [1, 3, 4]
 value = [15, 20, 30]
 test_2_wei_bag_problem1(bag_size, weight, value)

去

func test_2_wei_bag_problem1(weight, value []int, bagweight int) int {
 // 定义dp数组
 dp := make([][]int, len(weight))
 for i, _ := range dp {
  dp[i] = make([]int, bagweight+1)
 }
 // 初始化
 for j := bagweight; j >= weight[0]; j-- {
  dp[0][j] = dp[0][j-weight[0]] + value[0]
 }
 // 递推公式
 for i := 1; i < len(weight); i++ {
  //正序,也可以倒序
  for  j := weight[i];j<= bagweight ; j++ {
   dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]]+value[i])
  }
 }
 return dp[len(weight)-1][bagweight]
}

func max(a,b int) int {
 if a > b {
  return a
 }
 return b
}

func main() {
 weight := []int{1,3,4}
 value := []int{15,20,30}
 test_2_wei_bag_problem1(weight,value,4)
}

function testweightbagproblem (wight, value, size) {
  const len = wight.length,
    dp = array.from({length: len + 1}).map(
      () => array(size + 1).fill(0)
    );

  for(let i = 1; i <= len; i++) {
    for(let j = 0; j <= size; j++) {
      if(wight[i - 1] <= j) {
        dp[i][j] = math.max(
          dp[i - 1][j],
          value[i - 1] + dp[i - 1][j - wight[i - 1]]
        )
      } else {
        dp[i][j] = dp[i - 1][j];
      }
    }
  }

//   console.table(dp);

  return dp[len][size];
}

function testWeightBagProblem2 (wight, value, size) {
  const len = wight.length,
    dp = Array(size + 1).fill(0);
  for(let i = 1; i <= len; i++) {
    for(let j = size; j >= wight[i - 1]; j--) {
      dp[j] = Math.max(dp[j], value[i - 1] + dp[j - wight[i - 1]]);
    }
  }
  return dp[size];
}


function test () {
  console.log(testWeightBagProblem([1, 3, 4, 5], [15, 20, 30, 55], 6));
}

test();