背包问题_10.pdf

求方案数问题

二维情况

  1. 体积至多是j：初始化f[0][i] = 1，其余为0。
  2. 体积恰好是j：初始化f[0][0] = 1，其余为0。
  3. 体积至少是j：初始化f[0][0] = 1，其余为0。

一维情况

  1. 体积至多是j：初始化f[i] = 1。
  2. 体积恰好是j：初始化f[0] = 1，其余为0。
  3. 体积至少是j：初始化f[0] = 1，其余为0。

最大最小值问题

二维情况

  1. 体积至多是j：初始化f[i][j] = 0, i ∈[0, n], j ∈[0, m]，求最大价值
  2. 体积恰好是j：
    1. 求价值的最小值：初始化f[0][0] = 0，其余为INF
    2. 求价值的最大值：初始化f[0][0] = 0，其余为-INF
  3. 体积至少是j：初始化f[0][0] = 0，其余为INF，求最小价值

一维情况

  1. 体积至多是j：初始化f[i] = 0, i ∈[0, m]，求最大价值
  2. 体积恰好是j
    1. 求价值的最小值：初始化f[0] = 0，其余为INF
    2. 求价值的最大值：初始化f[0] = 0，其余为-INF
  3. 体积至少是j：初始化f[0] = 0，其余为INF，求最小价值