DP查缺补漏之01背包优化原理

先复习一下基本知识

• 状态假设
  • DP[I][J]为前\(i\)个物品，容量小于\(j\)时的最优解（最大价值）
• 状态转移
  • DP[I][J] = max(DP[I - 1][J], DP[I - 1][J - V[I]] + W[I])
    • 对于第\(i\)个物品，两种可能
      • 装入背包
        • 则状态应通过前\(i - 1\)个物品，容量小于\(j\)时的最优解再加上W[I]​转移，但是实际上本次状态的容量才为\(j\)，若直接从DP[I-1][J]转移则忽略了该物品体积，所以应从减去该次物品体积的DP[I - 1][J - V[I]]转移。即DP[I - 1][J - V[I]] + W[I]
        • 证明此解严谨性
          • 上一层循环已然计算了DP[I - 1][0 ~ M]的所有最优解
          • 则DP[I - 1][J - V[I]]已经是最优解
      • 不装入背包
        • 则状态应通过前\(i - 1\)个物品，容量小于\(j\)时的最优解直接进行转移
• 代码处理
  • 开二维数组来对标状态假设
  • 初始化DP[0][0~M]为\(0\)
  • 两层循环递推，外层枚举\(1 \sim i\)，内层枚举$ 1 \sim m $
  • 进行DP[I][J] = DP[I - 1][J - V[I]] + W[I]状态转移时必须确保\(J > V[I]\)

优化思路（空间）

• 从状态转移方程入手

  • DP[I][J] = max(DP[I - 1][J], DP[I - 1][J - V[I]] + W[I])
    • 每个DP[I][J]都是从DP[i-1][x]转移而来
    • 显然可以用滚动数组

• 具体化优化思路

  • 直接删除第一维

    • 用循环来直接进行对上一维的转移

    • for(int i=1;i<=n;i++)
      {
      	for(int j=W[i];j<=M;j++)
      	{
      		dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
      	}
      }
      

    • 但这有一个问题，此时的dp[j - w[i]]实际上就是本次\(i\)的，因为是从小到大递推的，要操作每一个dp[i - 1][j]的时候都已经被更新成此次状态的dp[i][j]了，此时需要一个妙手，第二层循环反着枚举

    • for(int i=1;i<=n;i++)
      {
      	for(int j=M;j>=w[i];j--)
      	{
      		dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
      	}
      }
      

    • 因为所有大的都是由小的转移而来，由大至小的枚举使得每一次要取dp[j-w[i]]时，dp[j-w[i]]都是\(i\)上一次循环的最优解，不会被更新。