入门级-01背包

# 背包问题

---
## 典型题目
|题目|
|----|
|[YBTJ1267 01背包问题](http://39.99.183.126:8888/p/YBTJ1267)|
|[NOIPJ2005C 采药](http://39.99.183.126:8888/p/NOIPJ2005C)|

---

## 基本模型：
一个容量为V的背包，在一定的限制条件下，放进最多（或最少）价值的东西。

根据限制条件的不同，分为三种情况：

* 01背包（ZeroOnePack）：每种物品只有一件，即只能选择放或者不放
* 完全背包（CompletePack）：每种物品有无限件
* 多重背包（MultiplePack）：每种物品最多有$n[i]$ 件可用

---

## 2、01背包动态规划

**基本模型**：一个容量为V的背包与N件物品，第i件物品的体积是c[i]，价值为w[i]，求将哪些物品装入背包可使得价值总和最大。

---
## 贪心思路
#### 基本步骤

1.  计算每种物品`单位重量的价值vi/wi`
2.  依贪心选择策略，将尽可能多的`单位重量价值最高`的物品装入背包。
3.  若将这种物品全部装入背包后，背包内的物品总重量未超过C，则选择单位重量价值次高的物品并尽可能多地装入背包。
4.  依此策略一直地进行下去，直到背包装满为止。

```c++
//n中物品已经排好序
void Knapsack(int n,float M,float v[],float w[],float x[])
{
       Sort(n,v,w);
       int i;
       for (i=1;i<=n;i++) x[i]=0;
       float c=M;
       for (i=1;i<=n;i++) {
          if (w[i]>c) break;
          x[i]=1;
          c-=w[i];
          }
       if (i<=n) x[i]=c/w[i];
}

```

算法knapsack的主要计算时间在于将各种物品依其单位重量的价值从大到小排序。因此，算法的计算时间上界为O（nlogn）。为了证明算法的正确性，还必须证明背包问题具有贪心选择性质。

---

#### 0-1背包问题不适用贪心算法

-   背包容量为50kg，物品1, 2和3的容量和价值分别为(10kg, 60), (20kg, 100)和(30kg, 120)。
    
-   单位重量价值最高的为物品1，6/kg, 其次是物品2 5/kg，最后是物品3 4/kg。

但是依照贪心算法首选物品1,然后选物品2，物品3不能再装入背包，最后背包内价值是160，显然不是最优解.  
![](https://i-blog.csdnimg.cn/blog_migrate/409f786009daf84431bcf37d65f00f2b.png)
最优解也显然是物品2和物品3,220。

-   对于0-1背包问题，贪心选择之所以不能得到最优解, 是因为在这种情况下，**无法保证最终能将背包装满**，`部分闲置的背包空间使每公斤背包空间的价值降低了`。
    
-   在考虑0-1背包问题时，应比较选择该物品和不选择该物品所导致的最终方案，然后再作出最好选择。
    
---
## 搜索可以吗？
上面的问题可以写个搜索算法，代码大致如下：
```c [1-14]
int ans = 0;
void search(int step, int sum, int left) // step 表示要处理第几个物品，sum表示现在包内总价值，left 表示包还有多少空间
{
    if(left < 0) return; //可行性剪枝
    if(sten > n)
    {
        ans = max(ans, sum);
	return;
    }
    //选第step个物品
    search(step + 1, sum + value[step], left - weight[step]);
    //不选
    search(step + 1, sum, left);
}
```

显然搜索的时间复杂度是$O(2^n)$。n稍大就会 $\color{blue}{\mathrm{TLE}}$。

$2^{27} = 134,217,728$
---

## DP

`维度`为：i件物品、j容量的背包

定义`状态`：设dp[i][j]表示把i件物品放入容量j的背包可获得的最大价值。

对于第i件物品（体积为c[i]，价值为w[i]）：

* 不放到背包里，则最大价值为dp[i-1][j]
* 放到背包里，则最大价值为dp[i-1][j-c[i]] + w[i]

`状态转移方程`为：

* 初始化：dp[0][j] = 0,  dp[i][0] = 0
* j < c[i]：dp[i][j] = dp[i-1][j]
* j>=c[i]：dp[i][j] = max(dp[i-1][j], dp[i-1][j-c[i]] + w[i])

---

## 3、理解过程

---

假设背包容量V=8，物品数量N=4：

|物品编号|1|2|3|4|
|---|---|---|---|---|
|体积c|2|3|4|5|
|价值w|3|4|5|6|

---

### 3.1 第一步：初始化

* dp[i][0]和dp[0][j]都为0
* 前两列体积c和价值w，为方便查询

---

|c|w|i\j|0|1|2|3|4|5|6|7|8
|---|---  |---| ---|---|---|---- | -----| -----| ----|----| ---|
|-|-|   0|0 |0|0|0|0|0|0|0|0|
|2|3|  1|0 |
|3|4|  2|0 |
|4|5|  3|0 |
|5|6|  4|0 |

---

### 3.2 第二步：怎么填？

* 1的列：由于1 < c[1]（体积为2）所以dp[1][1] = dp[1-1][1] = 0
  - 同样，dp[2][1]、dp[3][1]、dp[4][1]等都是0
* dp[1][2]：由于2==c[1], dp[1][2]=max(dp[1-1][2], dp[1-1][2-2] + 3) = 3
  - 理解：把1物品放进去，体积为2，获得价值为3
* dp[2][2]：由于2<c[2], dp[2][2] = dp[2-1][2] = 3
  - 理解：2物品放不进去，所以还是只能放一个1物品
* ....依次类推到dp[1][3]、dp[1][4]...、dp[1][8] 都为3

---

|c|w|i\j| 0|1  |2 |3  |4|5|6|7|8|
|---|---  |---|   ---|---  |---  |---   | ---| ---| ---|---| ---|
|-|-|   0|0 |0 |0  |0  |0|0|0|0|0|
|2|3|  1|0 |`0`|`3`|3 |3|3|3|3|3|
|3|4|  2|0 |`0`|`3`|
|4|5|  3|0 |`0`|`3`|
|5|6|  4|0 |`0`|`3`|

---

### 3.3 第三步：dp[2][3]

$dp[2][3] = max(dp[2-1][3], dp[2-1][3-c[2]]+w[2])=max(3, 0+4)=4$

* 理解：物品1或物品2都可以放进去，选择价值大的：
* 物品2放进去，则剩余容量为0，为dp[1][0] + w[2]=4
* 物品2不放进去，为dp[1][3]=3

---

c|w|i\j| 0|1 |2|`3` |4|5|6|7|8
-|-  |-|   -|-  |- |-  | -| -| -|-| -
-|-|   0|0 |0 |0 |0 |0|0|0|0|0
2|3|  1|`0` |0 |3 |`3` |3|3|3|3|3
`3`|`4`|  2|0 |0 | 3|`4`
4|5|  3|0 |0 |3 |
5|6|  4|0 |0 |3 |

---

dp[2][3]更直观的理解：

* 如果放进去
  - 本列第一行的3，减去本行的体积列(c[i])，结果为0
  - 找到上一行的0列的值，值为0
  - 0加上本行的价值列(w[i])，结果为4
* 如果不放进去：取上一行的本列的，值为3
* dp[2][3]填写4和3的最大值4

---

### 3.4 最后结果，按以上理解逐步填写

c|w|i\j| 0|1 |2|3 |4|5|6|7|8
-|-  |-|   -|-  |- |- | -| -| -|-| -
-|-|   0|0 |0 |0 |0|0|0|0|0|0
2|3|  1|0 |0 |3 |3|3|3|3|3|3
3|4|  2|0 |0 | 3|4|4|7|7|7|7 
4|5|  3|0 |0 |3 |4|5|7|8|9|9
5|6|  4|0 |0 |3 |4|5|7|8|9|10

最后，dp[4][8] = 10

---

## 4、关键代码

```c++
for(int i=1; i<=N; i++)
for(int j=1; j<=V; j++) {
  if(j >= c[i])
    dp[i][j] = max(dp[i-1][j], dp[i-1][j-c[i]] + w[i]);
  else
    dp[i][j] = dp[i-1][j];
}
```

---

# 优化

## 1、复杂度

以上动态规划的时间复杂度与空间复杂度均为O(N* V)。

但空间复杂度可以优化到O(m)，因为每一次状态转移只与上一行的值有关，我们可以：

* 状态只用一维数组
* 同一行里，从后往前填写，这样前面的值还被保留（上一行的值）

---

定义`状态`：设dp[j]表示把i件物品放入容量j的背包可获得的最大价值。

`状态转移方程`为：

* 初始化：dp[j] = 0
* j>=c[i]：dp[j] = max(dp[j], dp[j-c[i]] + w[i])

---

## 2、记录路径

如果想知道最大价值的方案里，背包里都放了哪些物品，该怎么做？

只要用一个二维数组path来存储每次更新放入的物品，然后从后往前遍历输出。

用path逆推出装入的物品：

* i从N、j从V往下倒序
* 如果Path[i][j]为1，表示被装入：
  - 输出物品i和价值，价值用括号
  - j = j - c[i]
* i = i - 1

如果使用二维状态，则无需path也可以倒推出装入的物品。

---

## 3、满背包

有时候，题目会要求背包刚好装满，这种情况与不装满的情况比，初始化不一样：

* 把dp[0][j]（j>0）初始化为负无穷大，表示背包没有装满。
* 把dp[0][i]初始化为0，表示装满了
* 当某个状态为不能装满时，值为负无穷，即使加上w[i]也算负无穷
* 判断某个状态，小于0就表示不能装满

在c++中，一般可用0x3f3f3f3f表示无穷大。

```c++
#define inf 0x3f3f3f3f;
```