# DP的背包问题小结-java语言描述

***

> 依然是复习以前学过的内容hhh

## 一、01背包

### 题目

一共有N件物品，第i（i从1开始）件物品的重量为w\[i]，价值为v\[i]。在总重量不超过背包承载上限W的情况下，能够装入背包的最大价值是多少？

### 分状态和转移方程

显然变量为装入的物品和背包的质量，所求的目标是最大的价值。

因此设`dp[i][j]`来表示将前i件物品在j的限重下的价值最大值。

对于每个状态`dp[i][j]`有两种情况：

1. 装入第i件物品（`dp[i-1][j-w[i]] + v[i]`）
2. 不装入 （`dp[i-1][j]`）

故转移方程为：

`dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])`

## 二、完全背包

### 题目

同01背包类似，但每种物品可以取无限个。

### 分析

和01背包类似，我们设出同样的dp状态，`dp[i][j]`来表示将前i种物品在j的限重下的价值最大值。

还是分两种情况：

1. 装入第i种物品，但和01背包不一样，这里装入一次以后还可以继续装入，所以应该转移到`dp[i][j-w[i]] + v[i]`而不是`dp[i-1][j-w[i]] + v[i]`。
2. 不装入第i种物品（还是`dp[i-1][j]`）

所以转移方程为：

`dp[i][j] = max(dp[i][j], dp[i-1][j-w[i]] + v[i])`

### 优化

这里可以做一个优化，可以通过滚动数组的方式，省去\[i]，压缩空间复杂度。

转移方程可改写为：`dp[j] = max(dp[j], dp[j-w[i]] + v[i])`

这里注意时间复杂度是不能被压缩的，而且这样写的前提是循环时`j`必须正向枚举，确保此时访问的`dp[j-[i]]`已经在本次循环中被计算到。

> 01背包也可以类似优化，只不过要逆向枚举，确保此时访问的`dp[j-[i]]`是上一次循环计算到的结果。

## 三、多重背包

### 题目

和完全背包不一样在于每种物品的数量是指定好的。一共有N种物品，第i（i从1开始）种物品的数量为n\[i]，重量为w\[i]，价值为v\[i]。在总重量不超过背包承载上限W的情况下，能够装入背包的最大价值是多少？

### 分析

因为指定了特定种类的物品数就相当于指定了n个独立的物品，所以多重背包问题可以直接化为01背包问题解决，其时间复杂度也不高。

转移方程可参考01背包。具体就是把给定数量的物品都视为单独的01背包里的物品来处理。

> 参考
>
> [动态规划之背包问题系列 - 知乎 (zhihu.com)](https://zhuanlan.zhihu.com/p/93857890)