动态规划

博主： Solost
发布时间：2023 年 01 月 10 日
505 次浏览
暂无评论
1720字数
分类： ACM笔记

# 动态规划

## 背包问题

### 01背包

![image-20220720134405717](https://amarantos475.oss-cn-hangzhou.aliyuncs.com/img/image-20220720134405717-16582958467481.png)

每个物品最多用一次

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

第 i 件物品的体积是 v~i~，价值是w~i~。

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

#### 输入格式

第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。

接下来有 N 行，每行两个整数 v~i~，w~i~，用空格隔开，分别表示第 i 件物品的体积和价值。

#### 输出格式

输出一个整数，表示最大价值。

#### 数据范围

0<N,V≤1000
0<v~i~，w~i~≤1000

#### 输入样例

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

#### 输出样例：

```
8
```

二维表示

```c++
#include <bits/stdc++.h>

using namespace std;
const int N = 1e3 + 10;
int n, m;
int v[N], w[N];
int f[N][N];
int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i ++) cin >> v[i] >> w[i];
  
    for(int i = 1; i <= n; i ++)
        for(int j = 0; j <= m; j ++){
            f[i][j] = f[i - 1][j];
            if(j >= v[i]) f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
        }
  
    cout << f[n][m];
    return 0;
}
```

优化为一维表示

```C++
#include <bits/stdc++.h>

using namespace std;
const int N = 1e3 + 10;
int n, m;
int v[N], w[N];
int f[N][N];
int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i ++) cin >> v[i] >> w[i];
  
    for(int i = 1; i <= n; i ++)//第一层循环主要用来表示方案数
        for(int j = 0; j <= m; j ++){//优化前
        for(int j = v[i]; j <= m; j ++)//因为我们下面判定为j >= vi所以可以省略0~vi
        for(int j = m; j >= v[i]; j --)//我们在判断max的时候需要判断前一层的条件f[i-1]，所以我们转换为一维的时候可以将第二层循环倒过来以达到降低维度的目的
            f[i][j] = f[i - 1][j];//优化前
            f[j] = f[j] //等价，删除即可
            if(j >= v[i]) f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
        }
  
    //最终优化后
    for(int i = 1; i <= n; i ++){
        for(int j = m; j >= v[i]; j -- ){
            f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
    }
  
    cout << f[n][m];
    return 0;
}
```

最终版

```C++
#include <bits/stdc++.h>

using namespace std;
const int N = 1010;
int v[N], w[N], f[N];
int n, m;
int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];
    for(int i = 1; i <= n; i ++)
        for(int j = m; j >= v[i]; j --){
            f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
  
    cout << f[m];
    return 0;
}
```

### 完全背包

每件物品有无限个

![image-20220720135502246](https://amarantos475.oss-cn-hangzhou.aliyuncs.com/img/image-20220720135502246-16582965040152.png)

最终的状态转移方程为 f[i, j] = f[i - 1, j - k * v[i]] + k * w[i];

![image-20220720145958200](https://amarantos475.oss-cn-hangzhou.aliyuncs.com/img/image-20220720145958200.png)

对比： 01背包问题状态转移方程为f[i, j] = max(f[i-1, j], f[i-1, j - v] + w);

```
完全背包问题状态转移方程 f[i, j] = max(f[i - 1, j], f[i, j - v] + w);
```

```C++
#include <bits/stdc++.h>

using namespace std;
const int N = 1010;
int f[N][N];
int v[N], w[N];
int main(){
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i ++) cin >> v[i] >> w[i];
    for(int i = 1; i <= n; i ++)
        for(int j = 0; j <= m; j ++)
            for(int k = 0; k * v[i] <= j; k ++){
                f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);
            }
              //我们可以发现规律由上图可知，可以将方程优化为f[i, j] = max(f[i-1, j], f[i][j - v] + w);
             //可以改写为
	for(int i = 1; i <= n; i ++)
        for(int j = 0; j <= m; j ++){
            f[i][j] = f[i - 1][j];
            if(j >= v[i]) f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i]);
        }
      //我们可以像01背包那样接着优化
    for(int i = 1; i <= n; i ++)
        for(int j = 0; j <= m; j ++){//2可以将j从vi开始，就可以去掉if
            f[i][j] = f[i - 1][j];//1删除一维变为f[j] = f[j];可以删去
            if(j >= v[i]) f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i]);//当删去一维时，f[i][j - v[i]] + w[i]可以直接去掉一维，因为j - v[i] <= j， j大于前面的，已经计算过，故可以直接删去
        }
          
```

最终版本

```c++
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int n, m;
int v[N], w[N];
int f[N];

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];

for (int i = 1; i <= n; i ++ )
        for (int j = v[i]; j <= m; j ++ )
            f[j] = max(f[j], f[j - v[i]] + w[i]);

cout << f[m] << endl;

return 0;
}
```

#### [NOIP2018]货币系统

#### 题目描述

在网友的国度中共有n种不同面额的货币，第i种货币的面额为a[i]，你可以假设每一种货币都有无穷多张。为了方便，我们把货币种数为n、面额数组为a[1..n]的货币系统记作(n,a)。
在一个完善的货币系统中，每一个非负整数的金额x 都应该可以被表示出，即对每一个非负整数x，都存在n个非负整数t[i] 满足a[i] x t[i] 的和为x。然而，在网友的国度中，**货币系统可能是不完善的**，即可能存在金额x不能被该货币系统表示出。例如在货币系统n=3, a=[2,5,9]中，金额1,3就无法被表示出来。
两个货币系统(n,a)和(m,b)是等价的，当且仅当**对于任意非负整数x，它要么均可以被两个货币系统表出，要么不能被其中任何一个表出。**
现在网友们打算简化一下货币系统。他们希望找到一个货币系统(m,b)，满足(m,b) 与原来的货币系统(n,a)等价，且m尽可能的小。他们希望你来协助完成这个艰巨的任务：找到最小的m。

#### 输入描述:

```
输入的第一行包含一个整数T,表示数据组数。接下来按照如下格式分别给出T组数据。
每组数据的第一行包含一个正整数n。接下来一行包含n个由空格隔开的正整数a[i]。
```

#### 输出描述:

```
输出文件共T行, 对于每组数据, 输出一行一个正整数, 表示所有与(n, a)等价的货币系统(m, b)中, 最小的m。              
```

#### 输入

```
2
4
3 19 10 6
5
11 29 13 19 17
```

#### 输出

```
2
5
```

#### 说明

```
在第一组数据中，货币系统(2, [3,10])和给出的货币系统(n, a)等价，并可以验证不存在m < 2的等价的货币系统，因此答案为2。
在第二组数据中，可以验证不存在m < n的等价的货币系统，因此答案为5。
```

```C++
#include <bits/stdc++.h>

using namespace std;
const int N = 110;
int a[N];
int f[25010];
int main(){
    int t;
    cin >> t;
    while(t --){
        int n;
        cin >> n;
        int ans = 0;
        memset(f, 0, sizeof f);
        for(int i = 1; i <= n; i ++) cin >> a[i];
        sort(a + 1, a + n + 1);
        for(int i = 1; i <= n; i ++){
            if(f[a[i]]) continue;
            ans++, f[a[i]] = 1;
            for(int j = a[i]; j <= a[n]; j++){
                if(f[j - a[i]]) f[j] = 1;
            }
        }
        cout << ans << endl;
    }
    return 0;
}
//分析题目，如果第i种货币可以去掉，那么可以推出有f[a[j]]已经存在，即货币可以由除去本身外其他种类的货币凑出，那么此种货币既可以被去掉，我们分析每种货币可以取无限次，且前一次可以推出后一次，想到可以用完全背包。我们枚举货币种类，再枚举从当前货币面额到最大面额，如果面额减去当前货币已经可以凑出，那么我们可以推出此面额也可以凑出。如果我们从最小面额枚举到最大面额时，如果出现未被标记的面额时，说明这张货币不可被替代，即ans++；从小到大排序是因为我们可以从小面额货币凑出大面额。
```

### 多重背包and多重背包（优化版）

每个物品的个数个数为有限个（题目给出）

#### 未使用二进制优化版本（暴力）

有 N 种物品和一个容量是 V 的背包。

第 ii 种物品最多有 s~i~ 件，每件体积是 vivi，价值是 wiwi。

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

#### 输入格式

第一行两个整数，N，VN，V，用空格隔开，分别表示物品种数和背包容积。

接下来有 NN 行，每行三个整数 vi,wi,sivi,wi,si，用空格隔开，分别表示第 ii 种物品的体积、价值和数量。

#### 输出格式

输出一个整数，表示最大价值。

#### 数据范围

0<N,V≤1000<N,V≤100
0<vi,wi,si≤1000<vi,wi,si≤100

#### 输入样例

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

#### 输出样例：

```
10
```

```C++
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110;

int n, m;
int v[N], w[N], s[N];
int f[N][N];

int main()
{
    cin >> n >> m;

for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i] >> s[i];

for (int i = 1; i <= n; i ++ )
        for (int j = 0; j <= m; j ++ )
            for (int k = 0; k <= s[i] && k * v[i] <= j; k ++ )
                f[i][j] = max(f[i][j], f[i - 1][j - v[i] * k] + w[i] * k);

cout << f[n][m] << endl;
    return 0;
}
```

#### 二进制优化版本（暴力）

有 N 种物品和一个容量是 V 的背包。

第 ii 种物品最多有 si件，每件体积是 vi，价值是 wi。

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

#### 输入格式

第一行两个整数，N，V 用空格隔开，分别表示物品种数和背包容积。

接下来有 N 行，每行三个整数 vi,wi,si用空格隔开，分别表示第 ii 种物品的体积、价值和数量。

#### 输出格式

输出一个整数，表示最大价值。

#### 数据范围

0<N≤1000
0<V≤2000
0<vi,wi,si≤2000

##### 提示：

本题考查多重背包的二进制优化方法。

#### 输入样例

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

#### 输出样例：

```
10
```

```C++
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 12010, M = 2010;  //一共有n个物品，每个物品最多拆分成logsi，所以数组大小为nlogsi

int n, m;
int v[N], w[N];
int f[M];

int main()
{
    cin >> n >> m;

int cnt = 0;
    for (int i = 1; i <= n; i ++ )
    {
        int a, b, s;
        cin >> a >> b >> s;
        int k = 1;
        while (k <= s)
        {
            cnt ++ ;
            v[cnt] = a * k;//这个过程相当于把si个物品分成1，2，4，8~~，相当于把si去掉等价为换成被分割物品选或者不选的问题，就成了01背包问题
            w[cnt] = b * k;
            s -= k;
            k *= 2;
        }
        if (s > 0)
        {
            cnt ++ ;
            v[cnt] = a * s;
            w[cnt] = b * s;
        }
    }

n = cnt;

for (int i = 1; i <= n; i ++ )
        for (int j = m; j >= v[i]; j -- )
            f[j] = max(f[j], f[j - v[i]] + w[i]);

cout << f[m] << endl;

return 0;
}
```

### 分组背包

每组中只多只能选一个

有 N 组物品和一个容量是 V 的背包。

每组物品有若干个，同一组内的物品最多只能选一个。
每件物品的体积是 v~ij~，价值是 w~ij~，其中 i 是组号，j 是组内编号。

求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。

输出最大价值。

#### 输入格式

第一行有两个整数 N，V，用空格隔开，分别表示物品组数和背包容量。

接下来有 N 组数据：

- 每组数据第一行有一个整数 S~i~，表示第 ii 个物品组的物品数量；
- 每组数据接下来有 Si行，每行有两个整数 vij,wij，用空格隔开，分别表示第 ii 个物品组的第 jj 个物品的体积和价值；

#### 输出格式

输出一个整数，表示最大价值。

#### 数据范围

0<N,V≤100
0<Si≤100
0<vij,wij≤100

#### 输入样例

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

#### 输出样例：

```
8
```

```C++
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110;

int n, m;
int v[N][N], w[N][N], s[N];
int f[N];

int main()
{
    cin >> n >> m;

for (int i = 1; i <= n; i ++ )
    {
        cin >> s[i];
        for (int j = 0; j < s[i]; j ++ )
            cin >> v[i][j] >> w[i][j];
    }

for (int i = 1; i <= n; i ++ )
        for (int j = m; j >= 0; j -- )
            for (int k = 0; k < s[i]; k ++ )
                if (v[i][k] <= j)
                    f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);

cout << f[m] << endl;

return 0;
}
```

最后修改：2023 年 01 月 10 日

如果觉得我的文章对你有用，请随意赞赏

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

动态规划

Solost • 2023 年 01 月 10 日

# 动态规划

## 背包问题

### 01背包

![image-20220720134405717](https://amarantos475.oss-cn-hangzhou.aliyuncs.com/img/image-20220720134405717-16582958467481.png)

每个物品最多用一次

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

第 i 件物品的体积是 v~i~，价值是w~i~。

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

#### 输入格式

第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。

接下来有 N 行，每行两个整数 v~i~，w~i~，用空格隔开，分别表示第 i 件物品的体积和价值。

#### 输出格式

输出一个整数，表示最大价值。

#### 数据范围

0<N,V≤1000
0<v~i~，w~i~≤1000

#### 输入样例

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

#### 输出样例：

```
8
```

二维表示

```c++
#include <bits/stdc++.h>

优化为一维表示

```C++
#include <bits/stdc++.h>

最终版

```C++
#include <bits/stdc++.h>

### 完全背包

每件物品有无限个

![image-20220720135502246](https://amarantos475.oss-cn-hangzhou.aliyuncs.com/img/image-20220720135502246-16582965040152.png)

最终的状态转移方程为 f[i, j] = f[i - 1, j - k * v[i]] + k * w[i];

![image-20220720145958200](https://amarantos475.oss-cn-hangzhou.aliyuncs.com/img/image-20220720145958200.png)

对比： 01背包问题状态转移方程为f[i, j] = max(f[i-1, j], f[i-1, j - v] + w);

```
完全背包问题状态转移方程 f[i, j] = max(f[i - 1, j], f[i, j - v] + w);
```

```C++
#include <bits/stdc++.h>

最终版本

```c++
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int n, m;
int v[N], w[N];
int f[N];

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];

for (int i = 1; i <= n; i ++ )
        for (int j = v[i]; j <= m; j ++ )
            f[j] = max(f[j], f[j - v[i]] + w[i]);

cout << f[m] << endl;

return 0;
}
```

#### [NOIP2018]货币系统

#### 题目描述

#### 输入描述:

#### 输出描述:

```
输出文件共T行, 对于每组数据, 输出一行一个正整数, 表示所有与(n, a)等价的货币系统(m, b)中, 最小的m。              
```

#### 输入

```
2
4
3 19 10 6
5
11 29 13 19 17
```

#### 输出

```
2
5
```

#### 说明

```C++
#include <bits/stdc++.h>

### 多重背包and多重背包（优化版）

每个物品的个数个数为有限个（题目给出）

#### 未使用二进制优化版本（暴力）

有 N 种物品和一个容量是 V 的背包。

第 ii 种物品最多有 s~i~ 件，每件体积是 vivi，价值是 wiwi。

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

#### 输入格式

第一行两个整数，N，VN，V，用空格隔开，分别表示物品种数和背包容积。

接下来有 NN 行，每行三个整数 vi,wi,sivi,wi,si，用空格隔开，分别表示第 ii 种物品的体积、价值和数量。

#### 输出格式

输出一个整数，表示最大价值。

#### 数据范围

0<N,V≤1000<N,V≤100
0<vi,wi,si≤1000<vi,wi,si≤100

#### 输入样例

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

#### 输出样例：

```
10
```

```C++
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110;

int n, m;
int v[N], w[N], s[N];
int f[N][N];

int main()
{
    cin >> n >> m;

for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i] >> s[i];

cout << f[n][m] << endl;
    return 0;
}
```

#### 二进制优化版本（暴力）

有 N 种物品和一个容量是 V 的背包。

第 ii 种物品最多有 si件，每件体积是 vi，价值是 wi。

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

#### 输入格式

第一行两个整数，N，V 用空格隔开，分别表示物品种数和背包容积。

接下来有 N 行，每行三个整数 vi,wi,si用空格隔开，分别表示第 ii 种物品的体积、价值和数量。

#### 输出格式

输出一个整数，表示最大价值。

#### 数据范围

0<N≤1000
0<V≤2000
0<vi,wi,si≤2000

##### 提示：

本题考查多重背包的二进制优化方法。

#### 输入样例

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

#### 输出样例：

```
10
```

```C++
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 12010, M = 2010;  //一共有n个物品，每个物品最多拆分成logsi，所以数组大小为nlogsi

int n, m;
int v[N], w[N];
int f[M];

int main()
{
    cin >> n >> m;

n = cnt;

for (int i = 1; i <= n; i ++ )
        for (int j = m; j >= v[i]; j -- )
            f[j] = max(f[j], f[j - v[i]] + w[i]);

cout << f[m] << endl;

return 0;
}
```

### 分组背包

每组中只多只能选一个

有 N 组物品和一个容量是 V 的背包。

每组物品有若干个，同一组内的物品最多只能选一个。
每件物品的体积是 v~ij~，价值是 w~ij~，其中 i 是组号，j 是组内编号。

求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。

输出最大价值。

#### 输入格式

第一行有两个整数 N，V，用空格隔开，分别表示物品组数和背包容量。

接下来有 N 组数据：

#### 输出格式

输出一个整数，表示最大价值。

#### 数据范围

0<N,V≤100
0<Si≤100
0<vij,wij≤100

#### 输入样例

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

#### 输出样例：

```
8
```

```C++
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110;

int n, m;
int v[N][N], w[N][N], s[N];
int f[N];

int main()
{
    cin >> n >> m;

for (int i = 1; i <= n; i ++ )
    {
        cin >> s[i];
        for (int j = 0; j < s[i]; j ++ )
            cin >> v[i][j] >> w[i][j];
    }

cout << f[m] << endl;

return 0;
}
```

动态规划

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

2023年中国高校计算机大赛-团队程序设计天梯赛（GPLT）上海理工大学校内选拔赛（同步赛) -F-坐火车

树状数组

动态规划

Codeforces Round 712 (Div. 1) - B. 3-Coloring

2023牛客寒假算法基础集训营2 L-Tokitsukaze and Three Integers

分数取模——费马小定理

Git基本操作

二分

AtCoder Beginner Contest 291 - E - Find Permutation

2023牛客暑期多校训练营5 - Nazrin the Greeeeeedy Mouse

动态规划

发表评论 取消回复 使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

动态规划

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款