若仅仅只看题解跳转part2

part1背包问题

01背包

01背包问题在网上也有很多解了。这里只说一些比较重要的，能够快速回忆关键点

• n为物品数，s为总容量

• dp[i][j]表示在遍历到第i个物品时，剩余容量为j时的背包的最大价值（很多人描述i为把前i个物品装入时的最大价值，但是index为i时，前i个物品并非全部装入了背包，而是有选择性的。这很容易误导新手）

• 因为我们使用j来表示背包的容量，所以j（而不是j-1）就表示容量为j，所以背包问题中所有的数组都建议从1开始，让0表示真正的“空”，而不是表示第一个！

• 因为上一点中强调了0表示真正的空，所以我们需要手动为“取物品为0个”和“容量为0”时进行手动初始化（因为在dp过程中，i和j从1开始，但因为有减法，仍然会出现i和j==0的情况，不初始化会溢出）

  //初始化
  //不选物品时，咋装都是0
  for (int j = 0; j <= s; j++)
  {
  dp[0][j] = 0;
  }
  //没有容量时，咋装都是0
  for (int i = 0; i <= n; i++)
  {
  dp[i][0] = 0;
  }

   

• 最后，就是dp过程的核心代码：

  for (int i = 1; i <= n; i++)
  {
     for (int j = 1; j <= s; j++)
          {
           if (j - w[i] >= 0)
           dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
           else
           dp[i][j] = dp[i - 1][j];
          }
  }

   

完全背包

01背包与完全背包的差异就是：完全背包的每个物品可以无限取。

我们直接从状态转移方程来理解：

• 01背包

  dp[i][j] = max(dp[i - 1][j],...