(1) 简单01背包题

问题描述

问题模型，$n$个物品，每个物品重量为$w[i]$，价值为$v[i]$，给定背包为载重量为$m$，求装的物品重量之和小于等于$m$，价值之和最大？

状态(问题定义)

$f[i][j]$，表示在前$i$个物品进行选取，所选的物品之和小于等于$j$，价值之和最大.

初始化

$f[0][0]$~$f[0][m]$ 为0

状态转移方程

$$f[i][j] = \begin{cases} f[i-1][j] & \text{if } j < w[i] \\ \max(f[i-1][j], f[i-1][j-w[i]] + v[i]) & \text{if } j \geq w[i] \end{cases}$$

$i:1 \sim n$ $j:0 \sim m$

答案

$f[n][m]$

(2) 简单01背包 恰好用完

问题描述

问题模型，$n$个物品，每个物品重量为$w[i]$，价值为$v[i]$，给定背包为载重量为$m$，求装的物品重量之和恰好等于$m$，价值之和最大？

状态(问题定义)

$f[i][j]$，表示在前$i$个物品进行选取，所选的物品重量之和等于$j$，价值之和最大.

初始化

$f[0][0]$ 为0 $f[0][1]$~$f[0][m]$ 为$-10^9$

状态转移方程

$$f[i][j] = \begin{cases} f[i-1][j] & \text{if } j < w[i] \\ \max(f[i-1][j], f[i-1][j-w[i]] + v[i]) & \text{if } j \geq w[i] \end{cases}$$

$i:1~n$ $j:0~m$

答案

$f[n][m]$ 小于0就无答案，否则就为$f[n][m]$

(3) 简单01背包 恰好用完的方案数

问题描述

问题模型，$n$个物品，每个物品重量为$w[i]$，给定背包为载重量为$m$，求装的物品重量之和恰好等于$m$的方案数？

状态(问题定义)

$f[i][j]$，表示在前$i$个物品进行选取，所选的物品重量之和等于$j$，方案数.

初始化

$f[0][0]$ 为1 其他为0

状态转移方程

$$f[i][j] = \begin{cases} f[i-1][j] & \text{if } j < w[i] \\ f[i-1][j] + f[i-1][j-v[i]] & \text{if } j \geq w[i] \end{cases}$$

$i:1~n$ $j:0~m$

答案

$f[n][m]$