动态规划--背包DP

动态规划--背包DP

Lionlnuc
Lionlnuc Lv4
  2026-03-09 2026-03-09 创建   2026-03-09 2026-03-09 更新      

01 背包

01背包问题

题目链接：
U225269 01背包问题 - 洛谷
思路：
设 f[i][j] 表示前 i 件物品放入容量为 j 的背包的最大价值。
如果当前物品不能放入, 此时没得选了，只能从前 i-1 件物品最优解转移过来，则 f[i][j]=f[i-1][j]。
如果能放入则比较价值：f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i])。
代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
const int N=1050;
int v[N],w[N];
int f[N][N];
void solve()
{
    int n,m;
    cin>>m>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>v[i]>>w[i];
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(j<v[i])f[i][j]=f[i-1][j];
            else f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i]);
        }
    }
    cout<<f[n][m]<<endl;
}

现在在时间上无法优化了，还可以优化空间。
可以将 f[i][j] 优化到一维 f[j] 表示 N 件物品，背包容量为 j 下的最优解。
为什么可以这样优化，可以看出每次求 f[i][j] 只依赖于 f[i-1][]，所以不需要保留之前的 f[i-2][] 等状态值。
一维情况下需要逆序遍历背包容量。当我们更新索引值较大的值时，需要用到之前的状态 f[j-v[i]]，要保证这个状态不被更新掉，例如我们在第 i 轮对体积为 4 的物品进行决策，则状态 f[8] 由 f[4] 更新而来，这里的 f[4] 应该是 f[i-1][4]，如果是正序枚举的话会变为 f[i][4]，所以我们需要逆序更新，使 f[4] 还没有在第 i 轮计算。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/*修改后的for循环*/
for(int i=1;i<=n;i++)
{
    for(int j=m;j>=0;j--)
    {
        if(j<v[i])f[j]=f[j];//优化后这句话没什么用了
        else{
            f[j]=max(f[j],f[j-v[i]]+w[i]);
        }
    }
}
/*
可以注意到只有j>=v[i]时才会进行更新，所以for循环还可以写为以下形式。
*/
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]);
    }
}
/*
由于我们在循环中是一个一个枚举的并不需要开两个数组，所以还可以优化输入
*/
for(int i=1;i<=n;i++)
{
    cin>>v>>w;
    for(int j=m;j>=v[i];j--)
    {
        f[j]=max(f[j],f[j-v]+w);
    }
}

采药

题目链接：
P1048 [NOIP 2005 普及组] 采药 - 洛谷
思路：
在这个题目中每种草药只有一株，时间 T 就是背包的容量，要实现价值的最大化。所以上一题代码即可通过。
代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define endl '\n'
const int N=1050;
int v[N],w[N];
int f[N];
void solve()
{
    int n,m;
    cin>>m>>n;
    // for(int i=1;i<=n;i++)
    // {
    //     cin>>v[i]>>w[i];
    // }
    // for(int i=1;i<=n;i++)
    // {
    //     for(int j=1;j<=m;j++)
    //     {
    //         if(j<v[i])f[i][j]=f[i-1][j];
    //         else f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i]);
    //     }
    // }
    // for(int i=1;i<=n;i++)
    // {
    //     for(int j=m;j>=0;j--)
    //     {
    //         if(j<v[i])f[j]=f[j];//优化后这句话没什么用了
    //         else{
    //             f[j]=max(f[j],f[j-v[i]]+w[i]);
    //         }
    //     }
    // }
    for(int i=1;i<=n;i++)
    {
        cin>>v[i]>>w[i];
        for(int j=m;j>=v[i];j--)
        {
            f[j]=max(f[j],f[j-v[i]]+w[i]);
        }
    }
    cout<<f[m]<<endl;
}
signed main(){
	IOS
	int t=1;
	while(t--)
	{
		solve();
	}
}

装箱问题

题目链接：
P1049 [NOIP 2001 普及组] 装箱问题 - 洛谷
思路：
要使箱子的剩余空间最小，那么就是使箱子的使用空间最大，也就是在不超过箱子体积的情况下，使其使用空间尽可能大，我们可以把 01 背包的价值修改为体积，这样计算得到的结果为不超过容量的情况下体积的最大值。
代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define endl '\n'
const int N=2e5+5;
int v,w;
int f[N];
void solve()
{
    int n,m;
    cin>>m>>n;
    
    for(int i=1;i<=n;i++)
    {
        cin>>v;
        for(int j=m;j>=v;j--){
            f[j]=max(f[j],f[j-v]+v);
        }
    }
    cout<<m-f[m]<<endl;
}
signed main(){
	IOS
	int t=1;
	while(t--)
	{
		solve();
	}
}

背包问题求方案数

题目链接：
U224067 背包问题求方案数 - 洛谷
代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define endl '\n'
const int N=1050;
int v[N],w[N];
int f[N][N];
void solve()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>v[i]>>w[i];
    }
    for(int i=n;i;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]);
        }
    }
    int i=1,j=m;
    while(i<=n){
        if(j>=v[i]&&f[i+1][j-v[i]]+w[i]>=f[i+1][j]){
            cout<<i<<" ";
            j-=v[i];
            i++;
        }else i++;
    }
}
signed main(){
	IOS
	int t=1;
	while(t--)
	{
		solve();
	}
}

背包问题求方案数

题目链接：
U224067 背包问题求方案数 - 洛谷
思路：
设 f[i] 表示背包容量为 i 时能装入物品的最大价值，c[i] 表示背包容量为 i 时最优选法的方案数。
代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
const int N=1010;
const int MOD=1e9+7;
int f[N];
int c[N];
void solve()
{
    int n,m;
    cin>>n>>m;
    int v,w;
    for(int i=0;i<=m;i++)c[i]=1;
    for(int i=1;i<=n;i++)
    {
        cin>>v>>w;
        for(int j=m;j>=v;j--)
        {
            if(f[j-v]+w>f[j]){
                f[j]=f[j-v]+w;
                c[j]=c[j-v];//方案数没有改变
            }else if(f[j-v]+w==f[j]){
                c[j]=(c[j-v]+c[j])%MOD;//装+不装
            }
        }
    }
    cout<<c[m];
}

背包问题求具体方案

题目链接：
U224072 背包问题求具体方案 - 洛谷
思路：
为了确保字典序最小，那么肯定是优先选前面的，所以我们从后向前遍历，让最优解落在 f[1][m]，然后从第一个开始向后搜索字典序 1 最小的路径方案。
设 f[i][j] 为从第 i 个物品到最后一个物品装入容量为 j 的背包的所有方案的最优解。
代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
const int N=1050;
int v[N],w[N];
int f[N][N];
void solve()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>v[i]>>w[i];
    }
    for(int i=n;i;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]);
        }
    }
    int i=1,j=m;
    while(i<=n){
        if(j>=v[i]&&f[i+1][j-v[i]]+w[i]>=f[i+1][j]){
            cout<<i<<" ";
            j-=v[i];
            i++;
        }else i++;
    }
}

数字组合

题目链接：
信息学奥赛一本通（C++版）在线评测系统
思路：
思路见代码注释。
代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define endl '\n'
const int N=150;
int a[N];
int f[N][10010];
/*
    背包容量为M，数值为体积，每个数都是一个物品。
    设f[i][j]表示前i个物品，总体积恰好为j的方案数。
    f[i][j]+=f[i-1][j];不选
    f[i][j]+=f[i-1][j-v];
*/
void solve()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        f[i][0]=1;//每个数字都不选时和为0也是种方案。
    }
    f[0][0]=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            f[i][j]+=f[i-1][j];
            if(j>=a[i])f[i][j]+=f[i-1][j-a[i]];
        }
    }
    cout<<f[n][m]<<endl;
}
signed main(){
	IOS
	int t=1;
	while(t--)
	{
		solve();
	}
}
/*
优化空间和输入。
*/
void solve()
{
    int n,m,v;
    cin>>n>>m;
    f[0]=1;
    for(int i=1;i<=n;i++)
    {
        cin>>v;
        for(int j=m;j>=v;j--)
        {
            f[j]+=f[j-v];
        }
    }
    cout<<f[m];
}

开心的金明

题目链接：
P1060 [NOIP 2006 普及组] 开心的金明 - 洛谷
思路：
01 背包
代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
const int N=2e5+5;
int f[N];
void solve()
{
    int n,m;
    cin>>n>>m;//输入钱数(体积)和个数
    for(int i=1;i<=m;i++)
    {
        int v,p;//价格 重要度
        cin>>v>>p;
        p*=v;
        for(int j=n;j>=v;j--){
            f[j]=max(f[j],f[j-v]+p);
        }
    }
    cout<<f[n];//f[钱]
}

二维费用背包

二维费用的背包问题

题目链接：
T426845 二维费用的背包问题 - 洛谷
代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define endl '\n'
const int N=2e5+5;
int v[N],w[N],m[N];
int f[110][110];
void solve()
{
    int n,V,M;
    cin>>n>>V>>M;
    for(int i=1;i<=n;i++)
    {
        cin>>v[i]>>m[i]>>w[i];
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=V;j>=v[i];j--)//枚举体积
        {
            for(int k=M;k>=m[i];k--)//枚举重量
            {
                f[j][k]=max(f[j][k],f[j-v[i]][k-m[i]]+w[i]);
            }
        }
    }
    cout<<f[V][M];
}
signed main(){
	IOS
	int t=1;
	while(t--)
	{
		solve();
	}
}

宠物小精灵之收服

题目链接：
U266184 宠物小精灵之收服 - 洛谷
思路：
二维费用 01背包，精灵球数量为第一费用，消耗的体力值为第二费用，最后要捕获的精灵数量最多。
设 f[i][j][k] 表示考虑前 i 个物品，第一维费用不超过 j 第二维费用不超过 k 的方案的最大价值。
分为选和不选两种情况：f[i][j][k]=max(f[i-1][j][k],f[i-1][j-v1][k-v2]+1)。
之后在遍历一遍求得满足最大数量情况下的最大体力值。
三维数组是一定会超内存的，所以优化为二维滚动数组去掉表示物品数量的 i。进行降维操作后对于两个费用的枚举需要倒序进行防止覆盖。
代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define endl '\n'
const int N=2e5+5;
int v[N],w[N];
int f[1100][550];
void solve()
{
    int n,m,t;//分别表示精灵球数、体力值、精灵数
    cin>>n>>m>>t;
    for(int i=1;i<=t;i++)
    {
        cin>>v[i]>>w[i];
    }
    for(int i=1;i<=t;i++)//精灵数
    {
        for(int j=n;j>=v[i];j--)//精灵球数
        {
            for(int k=m-1;k>=w[i];k--)//注意这里留一格体力不能消耗完。
            {
                f[j][k]=max(f[j][k],f[j-v[i]][k-w[i]]+1);
            }
        }
    }
    cout<<f[n][m-1]<<" ";
    for(int i=0;i<m-1;i++)
    {
        if(f[n][i]==f[n][m-1]){//找到第一个等于最大值的体力花费
            cout<<m-i;
            break;
        }
    }
}
signed main(){
	IOS
	int t=1;
	while(t--)
	{
		solve();
	}
}

潜水员

题目链接：
U291791 潜水员 - 洛谷
思路：
这个题目和之前的差别是要求不少于费用。所以设 f[i][j][k] 表示考虑前 i 个物品，第一维费用不低于 j，第二维费用不低于 k 的方案。
在枚举氮气和氧气费用时不需要设限了。因为可以超载。
状态转移公式：
不选的话就是 f[i][j][k]=f[i-1][j][k]。
选 f[i][j][k]=min(f[i][j][k],f[i-1][j-v1][k-v2]) 注意这里的下标不能低于 0。
仍然优化空间。
代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define endl '\n'
const int N=2e5+5;
int v[N],w[N],m[N];
int f[110][110];
void solve()
{
    int n,M;//分别表示氧气氮气费用
    cin>>n>>M;
    int t;
    cin>>t;
    memset(f,0x3f,sizeof f);
    for(int i=1;i<=t;i++)//这里还可以优化输入放到下面的循环中。
    {
        cin>>v[i]>>m[i]>>w[i];//分别表示氧气/氮气/气缸重量
    }
    f[0][0]=0;
    for(int i=1;i<=t;i++)
    {
        for(int j=n;j>=0;j--)//枚举氧气
        {
            for(int k=M;k>=0;k--)//枚举氮气
            {
                f[j][k]=min(f[j][k],f[max(j-v[i],0LL)][max(k-m[i],0LL)]+w[i]);
            }
        }
    }
    cout<<f[n][M];
}
signed main(){
	IOS
	int t=1;
	while(t--)
	{
		solve();
	}
}

完全背包

完全背包问题

题目链接：
U200606 完全背包问题 - 洛谷
思路：
设 f[i][j] 表示从前 i 个物品中选择，总体积不超过 j 的所有方案的最大值。
完全背包和 01 背包不同的地方就在于同一个物品它可以选不止一个。
状态转移：
如果不选这个物品那么 f[i][j]=f[i-1][j] 这是比较好想的。
如果要选的话 $f_{i,j}=max_{k=0}^{\infty}(f_{i-1,j-vk}+wk)。这样的三重循环时间复杂度太高，我们观察一下$
f_{i,j}=max(f_{i-1,j},f_{i-1,j-v}+w,….,f_{i-1,j-kv}+wk)

f_{i,j-v}=max(f_{i-1,j-v},f_{i-1,j-2*v}+w,…,f_{i-1,j-(k-1)*v}+(k-1)*w)
$$
所以状态转移可以优化为 。
我们可以对比一下 01 背包和完全背包的状态转移公式：

1
2
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);

再用二维降一维的思路就得到最终的状态转移方程：f[j]=max(f[j],f[j-v]+w)。
和 01 背包不同的是这里不用逆序，因为 01 背包顺推会覆盖掉之前的状态，在完全背包中我们可以用到这层的状态，所以可以顺推。
代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define endl '\n'
const int N=1010;
int v,w;
int f[N];
/*
void solve()//二维写法
{
    int n,m;//分别表示物品种数和背包容积
    cin>>m>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>v>>w;
        for(int j=1;j<=m;j++)
        {
            f[i][j]=f[i-1][j];
            if(j>=v)f[i][j]=max(f[i][j],f[i][j-v]+w);
        }
    }
    cout<<"max="<<f[n][m];
}*/
void solve2()//一维写法
{
    int n,m;//分别表示物品种数和背包容积
    cin>>m>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>v>>w;
        for(int j=1;j<=m;j++)
        {
            if(j>=v)f[j]=max(f[j],f[j-v]+w);
        }
    }
    cout<<"max="<<f[m];
}
signed main(){
	IOS
	int t=1;
	while(t--)
	{
		solve2();
	}
}

买书

题目链接：
T171705 买书方案 - 洛谷
思路：
设 f[i] 为当前消费 i 的方案数。和数字组合很像。
代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
const int N=1010;
int f[N];
int a[5]={0,10,20,50,100};
void solve()
{
    int n;
    cin>>n;
    f[0]=1;
    for(int i=1;i<=4;i++)
    {
        for(int j=a[i];j<=n;j++){
                f[j]+=f[j-a[i]];
        }
    }
    if(n==0)cout<<"0";
    else cout<<f[n];
}

货币系统

题目链接：
P5020 [NOIP 2018 提高组] 货币系统 - 洛谷
思路：
考虑每个 a[i] 是否能被之前的数表示，如果可以那么就不需要这个数。所以遍历数组，如果当前数的被表示次数不为 1 则能够被其它数表示出来。
代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
const int N=110;
const int M=25005;
int a[N];
int f[M];
void solve()
{
    int n;
    cin>>n;
    memset(f,-0x3f,sizeof f);
    for(int i=1;i<=n;i++)cin>>a[i];
    f[0]=0;
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=a[i];j<M;j++){
            f[j]=max(f[j],f[j-a[i]]+1);
        }
    }
    for(int i=1;i<=n;i++){
        if(f[a[i]]==1)ans++;
    }
    cout<<ans<<endl;
}

多重背包

朴素多重背包：（适合在物品数量少的时候使用）
状态表示：f[i][j] 表示从前 i 个物品中选总体积不超过 j 的方案的最大价值。和完全背包不同的是有数量限制，所以在枚举时需要添加限制。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/*二维版本*/
void solve(){
    cin>>n>>m;//表示物品数量和背包容量
    int v,w,s;//分别表示体积、价值、数量
    for(int i=1;i<=n;i++)
    {
        cin>>v>>w>>s;
        for(int j=0;j<=m;j++)
        {
            for(int k=0;k<=s&&k*v<=j;k++)
            {
                f[i][j]=max(f[i][j],f[i-1][j-k*v]+w*k);
            }
        }
    }
    cout<<f[n][m];
}
/*优化到一维*/
void solve(){
    cin>>n>>m;//表示物品数量和背包容量
    int v,w,s;//分别表示体积、价值、数量
    for(int i=1;i<=n;i++)
    {
        cin>>v>>w>>s;
        for(int j=m;j>=v;j--)
        {
            for(int k=0;k<=s&&k*v<=j;k++)
            {
                f[j]=max(f[j],f[j-k*v]+w*k);
            }
        }
    }
    cout<<f[m];
}

二进制优化：
当物品个数很多时，一个一个枚举并不合适。利用倍增思想和二进制，可以知道一个十进制数是可以转化为一个二进制比特串，进而可以表示为 和的形式。比如一个物品有 10 个那可以拆分成 ，这样可以拆分成三个箱子，一个有 8 个物品，一个有 2 个物品，转化为 01 背包的思路，只需要判断这个箱子选不选就可以了。
这里注意一下，我们相当于是吧每个物品都划分成了 +1个箱子，这样一共 N 个数最后数组需要开 ，所以 f 数组肯定不能开二维了。
拆分之后其实就是 cnt 个背包。之后运用 01 背包代码求解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
int v[M],w[M];
int f[M];
void solve(){
    int n,m;
    cin>>n>>m;
    int cnt=1;
    for(int i=1;i<=n;i++)
    {
        int a,b,s;
        cin>>a>>b>>s;
        for(int j=1;j<=s;j<<=1){//进行二进制拆分
            v[cnt]=j*a;
            w[cnt++]=j*b;
            s-=j;
        }
        if(s){//处理剩余
            v[cnt]=s*a;
            w[cnt++]=s*b;
        }
    }
    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;
}

单调队列：
题目链接：
P1886 【模板】单调队列 / 滑动窗口 - 洛谷
思路：
暴力做法就是以 f[i] 为以 i 结尾的窗口的最小值，用两重循环去做。
可以使用单调队列将第二层枚举优化掉。
单调队列：队头出队，队尾进队出队。当队列不空且新元素更优时，旧元素从队尾出队。每个元素必然从队尾入队一次。当队头元素滑出窗口时，从队头出队。
在队列中存储数组下标方便判断队头出队。
代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
const int N=1e6+5;
int a[N];
int q[N];
void solve()//一维写法
{
    int n,k;
    cin>>n>>k;
    int h=1,t=0;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    for(int i=1;i<=n;i++)
    {
        while(h<=t&&a[q[t]]>=a[i])t--;//队列不空且新元素更优时队尾出队
        q[++t]=i;//队尾入队
        if(q[h]<i-k+1)h++;//队头元素滑出窗口
        if(i>=k)cout<<a[q[h]]<<" ";
    }
    cout<<endl;
    h=1,t=0;
    for(int i=1;i<=n;i++)
    {
        while(h<=t&&a[q[t]]<=a[i])t--;//队列不空且新元素更优时队尾出队
        q[++t]=i;//队尾入队
        if(q[h]<i-k+1)h++;//队头元素滑出窗口
        if(i>=k)cout<<a[q[h]]<<" ";
    }
}

连续子序列的最大和：
题目链接：
信息学奥赛一本通（C++版）在线评测系统
思路：
使用单调队列+前缀和数组，区间范围为 m，队列首元素为区间最小值，用区间内的前缀和减去最小值得到序列中的最大值。
代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void solve()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        s[i]=s[i-1]+a[i];
    }
    int h=0,t=0,ans;
    q[0]=0,ans=s[1];
    for(int i=1;i<=n;i++)
    {
        if(h<=t&&q[h]<i-m)h++;//队头出队。队列中储存的是前缀和数组下标所以减一
        ans=max(ans,s[i]-s[q[h]]);//使用队头最小值计算
        while(h<=t&&s[q[t]]>=s[i])t--;//队列不空且新元素更
        q[++t]=i;
    }
    cout<<ans;
}

单调队列优化：
通过在朴素版本添加输出观察可得，f 数组是按类更新的，可以把 f[0...m] 按体积 v 的余数划分成 v 个类。
f[j] 是由前面不超过 s 的同类值递推得到的，相当于从前面宽度为 s 的窗口挑选最大值来更新当前值。所以用单调队列来维护最大值。
代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
int f[M],g[M];
int q[M];
int v,w,s;
void solve(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        memcpy(g,f,sizeof f);//将f拷贝到g
        cin>>v>>w>>s;
        for(int j=0;j<v;j++)//分成v个类
        {
            int h=0,t=-1;
            for(int k=j;k<=m;k+=v)//对每个类使用单调队列
            {
                //当q[h]不在窗口[k-s*v,k-v]时出队
                if(h<=t&&q[h]<k-s*v)h++;
                //使用队头最大值更新f
                if(h<=t)f[k]=max(g[k],g[q[h]]+(k-q[h])/v*w);
                //当前值更大队尾出队
                while(h<=t&&g[k]>=g[q[t]]+(k-q[t])/v*w)t--;
                q[++t]=k;
            }
        }
    }
    cout<<f[m];
}

庆功会

题目链接：
U200694 庆功会 - 洛谷
思路：
多重背包模板题。
代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
const int N=6050;
int f[N][N];//表示考虑前i种物品，价格不超过j的方案的最大价值
void solve()
{
    int n,m;
    cin>>n>>m;//分别表示奖品种数和金额
    for(int i=1;i<=n;i++)
    {
        int v,w,s;
        cin>>v>>w>>s;//分别表示价格价值数量(多重背包)
        for(int j=1;j<=m;j++)
        {
            for(int k=0;k<=s&&j>=k*v;k++)
            {
                f[i][j]=max(f[i][j],f[i-1][j-k*v]+w*k);
            }
        }
    }
    cout<<f[n][m];
}
/*一维版本*/
const int N=6050;
int f[N];//表示考虑前i种物品，价格不超过j的方案的最大价值
void solve()
{
    int n,m;
    cin>>n>>m;//分别表示奖品种数和金额
    for(int i=1;i<=n;i++)
    {
        int v,w,s;
        cin>>v>>w>>s;//分别表示价格价值数量(多重背包)
        for(int j=m;j>=v;j--)
        {
            for(int k=0;k<=s&&j>=k*v;k++)
            {
                f[j]=max(f[j],f[j-k*v]+w*k);
            }
        }
    }
    cout<<f[m];
}

分组背包

分组背包问题

题目链接：
U280369 分组背包问题 - 洛谷
思路：
用 f[i][j] 表示前 i 组物品放入容量为 j 的背包的方案集合的最大值。
对于第 i 组物品有以下 s+1 种方案：
1）一个都不选，f[i][j]=f[i-1][j]。
2）选第 i 组的第 1 个物品，f[i][j]=f[i-1][j-v[1]]+w[1]。
…
s+1）选第 i 组的第 k 个物品，f[i][j]=f[i-1][j-v[k]]+w[k]。
所以状态转移公式为 f[i][j]=max(f[i][j],f[i-1][j-v[k]]+w[k]) 。
代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
const int N=110;
int s[N];
int v[N][N],w[N][N];
int f[N][N];
void solve()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>s[i];
        for(int j=1;j<=s[i];j++)cin>>v[i][j]>>w[i][j];
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=m;j++)
        {
            for(int k=0;k<=s[i]&&j>=v[i][k];k++)
            {
                f[i][j]=max(f[i][j],f[i-1][j-v[i][k]]+w[i][k]);
            }
        }
    }
    cout<<f[n][m];
}
/*一维数组版本*/
void solve()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>s[i];
        for(int j=1;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]&&j>=v[i][k];k++)
                f[j]=max(f[j],f[j-v[i][k]]+w[i][k]);
        }
    }
    cout<<f[m];
}

机器分配

题目链接：
P2066 机器分配 - 洛谷
思路：
这个题目也可可以转换为分组背包问题，把每个公司看成一个分组。求具体方案类比于上面的 01 背包求具体方案，倒着枚举让最优解落到 f[1][m]，同时记录记录 f[i][j] 取到最大值时，第 i 家公司占有的机器数量。
反向DP先决策后面的公司再决策前面的公司，当盈利相等时，保留前面公司（编号小）分配更少的方案。这里是 <。当使用 <= 时得到的答案就是编号小的公司尽量多分配。
代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
const int N=100;
int f[N][N];
int w[N][N];
int way[N][N];
void solve()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)cin>>w[i][j];
    }
    for(int i=n;i;i--)
    {
        for(int j=1;j<=m;j++)
        {
            for(int k=0;k<=j;k++)
            {
                if(f[i][j]<f[i+1][j-k]+w[i][k]){
                    f[i][j]=f[i+1][j-k]+w[i][k];
                    way[i][j]=k;
                }
            }
        }
    }
    cout<<f[1][m]<<endl;
    for(int i=1,j=m;i<=n;i++)
    {
        cout<<i<<" "<<way[i][j]<<endl;
        j-=way[i][j];
    }
}

金明的预算方案

题目链接：
P1064 [NOIP 2006 提高组] 金明的预算方案 - 洛谷
思路：
本质也是分组背包，每个主件代表一个组，附件是组中的物品。这样一个主件最多两附件，所以最多四种选法（一主、一主一附(两种)、一主两附、），这里用到了二进制思想去优化，具体见代码注释。
代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define endl '\n'
#define PII pair<int,int>
#define x first
#define y second
const int N=2e5+5;
PII a[N];//主件
vector<PII> b[N];//附件，用pair存体积和对应主件
int f[N];
void solve()
{
    int n,m;
    cin>>m>>n;
    for(int i=1;i<=n;i++)
    {
        int v,p,q;
        cin>>v>>p>>q;
        p*=v;
        if(!q)a[i]={v,p};//主件
        else b[q].push_back({v,p});//附件
    }
     //f[i][u]：前i个组中，体积不超过u的最大价值。
    for(int i=1;i<=n;i++)
    {
        if(!a[i].x)continue;
        for(int u=m;u>=0;u--)
        {
            for(int j=0;j<1<<b[i].size();j++)
            /*
	            这里枚举附件数量，当附件数量为0时就不进行循环了。当附件为1时一共有2种(主(00)、主附(01))、附件数为2时(00\01\10\11)二进制思路
            */
            {
                int v=a[i].x,w=a[i].y;//主件的体积和价值
                for(int k=0;k<b[i].size();k++)//二进制枚举
                {
                    if(j>>k&1)//判断第k位是否为1，k只能为0和1
                    {
                        v+=b[i][k].x;//如果选了这个则加上对应附件的体积价值
                        w+=b[i][k].y;
                    }
                }
                if(u>=v)f[u]=max(f[u],f[u-v]+w);//如果当前剩余的容量大于当前组合的体积更新价值
            }
        }
    }
    cout<<f[m];
}
signed main(){
	IOS
	int t=1;
	while(t--)
	{
		solve();
	}
}

混合背包

题目链接：
T302125 混合背包 - 洛谷
代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define endl '\n'
#define PII pair<int,int>
const int N=1010;
int v[N],s[N],w[N];
int f[N];
void solve()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>v[i]>>w[i]>>s[i];
    }
    for(int i=1;i<=n;i++)
    {
        if(!s[i])//完全背包
        {
            for(int j=v[i];j<=m;j++){
                f[j]=max(f[j],f[j-v[i]]+w[i]);
            }
        }
        else{
            if(s[i]==1){//01背包
                for(int j=m;j>=v[i];j--)
                {
                    f[j]=max(f[j],f[j-v[i]]+w[i]);
                }
            }else{//多重背包
                for(int k=1;k<=s[i];k<<=1)
                {
                    for(int j=m;j>=v[i]*k;j--){
                        f[j]=max(f[j],f[j-k*v[i]]+k*w[i]);
                    }
                    s[i]-=k;
                }
                if(s[i]){
                    for(int j=m;j>=v[i]*s[i];j--){
                        f[j]=max(f[j],f[j-s[i]*v[i]]+w[i]*s[i]);
                    }
                }
            }
        }
    }
    cout<<f[m];
}
signed main(){
	IOS
	//int t;
	//cin>>t;
	int t=1;
	while(t--)
	{
		solve();
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define endl '\n'
#define PII pair<int,int>
const int N=1010;
int f[N];
int c[N*8],w[N*8];
int idx=1;
void solve()
{
    int n,m;
    cin>>n>>m;
    int v,W,s;
    for(int i=1;i<=n;i++)
    {
        cin>>v>>W>>s;
        if(s==0)s=m/v;//对于完全背包其实在背包容量限制下也为多重背包。
        for(int j=1;j<=s;j<<=1){
            c[idx]=j*v;
            w[idx++]=j*W;
            s-=j;
        }
        if(s){
            c[idx]=s*v;
            w[idx++]=s*W;
        }
    }
    //最后来一个01背包
    for(int i=1;i<=idx;i++)
    {
        for(int j=m;j>=c[i];j--){
            f[j]=max(f[j],f[j-c[i]]+w[i]);
        }
    }
    cout<<f[m];
}
signed main(){
	IOS
	//int t;
	//cin>>t;
	int t=1;
	while(t--)
	{
		solve();
	}
}

有依赖的背包问题

题目链接：
U436983 有依赖的背包问题 - 洛谷
代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define endl '\n'
#define PII pair<int,int>
int n,m,root;
const int N=110;
int h[N],e[N],ne[N],idx;
int v[N],w[N];
int f[N][N];
void add(int a,int b){
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}
void dfs(int u){
    for(int i=h[u];i!=-1;i=ne[i]){
        int s=e[i];
        dfs(s);
        for(int j=m-v[u];j>=0;j--){
            for(int k=0;k<=j;k++)
            {
                f[u][j]=max(f[u][j],f[u][j-k]+f[s][k]);
            }
        }
    }
    for(int j=m;j>=v[u];j--)f[u][j]=f[u][j-v[u]]+w[u];
    for(int j=0;j<v[u];++j)f[u][j]=0;
}
void solve()
{
    memset(h,-1,sizeof h);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        int p;
        cin>>v[i]>>w[i]>>p;
        if(p==-1)root=i;
        else add(p,i);
    }
    dfs(root);
    cout<<f[root][m];
}
signed main(){
	IOS
	//int t;
	//cin>>t;
	int t=1;
	while(t--)
	{
		solve();
	}
}
  • 标题: 动态规划--背包DP
  • 作者: Lionlnuc
  • 创建于 : 2026-03-09 00:00:00
  • 更新于 : 2026-03-09 00:00:00
  • 链接: https://lionlnuc.github.io/2026/03/09/动态规划——背包DP/
  • 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。
评论
目录
动态规划--背包DP
  1. 01 背包
    1. 01背包问题
    2. 采药
    3. 装箱问题
    4. 背包问题求方案数
    5. 背包问题求方案数
    6. 背包问题求具体方案
    7. 数字组合
    8. 开心的金明
  2. 二维费用背包
    1. 二维费用的背包问题
    2. 宠物小精灵之收服
    3. 潜水员
  3. 完全背包
    1. 完全背包问题
    2. 买书
    3. 货币系统
  4. 多重背包
    1. 庆功会
  5. 分组背包
    1. 分组背包问题
    2. 机器分配
    3. 金明的预算方案
  6. 混合背包
  7. 有依赖的背包问题