# 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)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://blog.mcyou.cc/suan-fa-xiang-guan/suan-fa/dp-de-bei-bao-wen-ti-xiao-jie-java-yu-yan.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.