# 背包问题

```yaml
   Author: Gentleman.Hu
   Create Time: 2020-11-08 12:39:42
   Modified by: Gentleman.Hu
   Modified time: 2020-11-08 13:10:13
   Email: justfeelingme@gmail.com
   Home: https://crushing.xyz
   Description: 对背包问题的探索与学习
```

## 背包问题

> <https://www.acwing.com/problem/content/2/>

### 问题描述

有N件物品和一个容量是V的背包.每件物品只能使用一次.

有i件物品的体积是Vi,价值是Wi.

求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大. 输出最大价值.

**输入格式** 第一行两个整数,N,V,用空格隔开,分别表示物品数量和背包容积.

接下来有N行,每行两个整数Vi,Wi,用空格隔开,分别表示第i件物品的体积和价值.

**输出格式** 输出一个整数,表示最大价值.

**数据范围** 0\<N,V<=1000 0\<Vi,Wi<=1000

输入样例

```
4 5
1 2
2 4
3 4
4 5
```

输出样例:

```
8
```

### Soltion

> [一维动态规划状态转移方程解释](https://www.acwing.com/solution/content/3982/)