首页 > 基础资料 博客日记

DP——背包DP

2026-04-02 20:00:02基础资料围观1次

极客资料网推荐DP——背包DP这篇文章给大家，欢迎收藏极客资料网享受知识的乐趣

动态规划——背包问题全总结

关于动态规划的背包问题，可分为：

  1. 0/1 背包问题
  2. 分组背包问题
  3. 多重背包问题
  4. 完全背包问题

1 0/1背包问题

问题描述

有 \(N\) 件物品和一个容量是 \(V\) 的背包。每件物品只能使用一次。
第 \(i\) 件物品的体积是 \(v_i\)，价值是 \(w_i\)。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。

输入描述：
第一行两个整数 \(N,V\)，用空格隔开，分别表示物品数量和背包容积。
接下来有 \(N\) 行，每行两个数 \(v_i, w_i\)，用空格分隔开，表示该物体的体积和价值。

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

分析

引入一个 \((N+1) \times (V+1)\) 的二维数组 \(dp[][]\)。
\(dp[i][j]\) 表示把前 \(i\) 个物品【\(1,i\)】装入容量为 \(j\) 的背包中获得最大价值。
把每个 \(dp[i][j]\) 都看做一个背包；容量为 \(j\)，装 \(1 \sim i\) 这些物品，最后的 \(dp[N][V]\) 为问题答案。

dp 转移方程

  1. 第 \(i\) 个物品的体积比容量 \(j\) 还大，不能装进背包。直接继承前 \(i-1\) 个物品装进容量为 \(j\) 的背包情况即可，即

\[dp[i][j]=dp[i-1][j] \]

  1. 第 \(i\) 个物品的体积比容量 \(j\) 小，能装进背包，又可以分成两种情况：装或不装：
    ① 装第 \(i\) 个物品：

\[dp[i][j]=dp[i-1][j-v[i]]+w[i] \]

② 不装第 \(i\) 个物品：

\[dp[i][j]=dp[i-1][j] \]

取两者的最大值：

\[dp[i][j]=\max(dp[i-1][j],\ dp[i-1][j-v[i]]+w[i]) \]

递推代码（暴力做法）

#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int w[N], v[N]; // 物品的价值和体积
int dp[N][N];

int solve(int n, int V) {
    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= V; j++) {
            if (v[i] > j)
                dp[i][j] = dp[i - 1][j];  // 第i个物品比背包大，装不了
            else
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i]); // 能装
        }
    return dp[n][V];
}

int main() {
    int n, V;
    scanf("%d%d", &n, &V);
    for (int i = 1; i <= n; i++)
        scanf("%d%d", &v[i], &w[i]);
    printf("%d", solve(n, V));
    return 0;
}

记忆化搜索（暴力做法）

#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int w[N], v[N];
int dp[N][N];

int solve(int i, int j) {
    if (dp[i][j] != 0)
        return dp[i][j];
    if (i == 0)
        return 0;
    int res;
    if (v[i] > j)
        res = solve(i - 1, j);
    else
        res = max(solve(i - 1, j), solve(i - 1, j - v[i]) + w[i]);
    return dp[i][j] = res;
}

int main() {
    int n, V;
    scanf("%d%d", &n, &V);
    for (int i = 1; i <= n; i++)
        scanf("%d%d", &v[i], &w[i]);
    printf("%d", solve(n,V));
    return 0;
}

滚动数组优化

\(dp[i][]\) 只与 \(dp[i-1][]\) 有关，与其他没有关系。
使用覆盖，有如下两种方式：

1.1 交替滚动

定义 \(dp[2][j]\)，用 \(dp[0][\ ]\) 和 \(dp[1][\ ]\) 交替滚动。
在如下代码中，\(now\) 指向正在计算的最新一行，\(old\) 指向已经计算过的旧的一行。
在递推关系中，\(now\) 相当于 \(i\)，\(old\) 相当于 \(i-1\)。

int dp[2][N];
int solve(int n, int V) {
    int now=0,old=1;
    for(int i=1;i<=n;i++)
    {
        swap(old,now);  // 交替转换
        for(int j=0;j<=V;j++)
        {
            dp[now][j]=dp[old][j];
            if(v[i]<=j)
            dp[now][j]=max(dp[old][j],dp[old][j-v[i]]+w[i]);
        }
    }
    return dp[now][V]; // 返回最新的行
}

完整代码：

#include <bits/stdc++.h>
using namespace std;
int n, m;
const int N = 1010;
int dp[2][N];
int v[N], w[N];

int main() {
    scanf("%d%d", &m, &n);
    for (int i = 1; i <= n; i++)
        scanf("%d%d", &v[i], &w[i]);
        
    int old = 1, ne = 0;
    for (int i = 1; i <= n; i++) {
        swap(old, ne); // 交替上一列与下一列
        for (int j = 1; j <= m; j++) {
            dp[ne][j] = dp[old][j]; // 将旧状态转移
            if (v[i] <= j)
                dp[ne][j] = max(dp[ne][j], dp[old][j - v[i]] + w[i]);
        }
    }
    printf("%d", dp[ne][m]); // 输出新状态
    return 0;
}

1.2 自我滚动

原理和上述类似

int dp[N];
int solve(int n,int V)
{
    for(int i=1;i<=n;i++)
    for(int j=V;j>=v[i];j--)
    dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
    return dp[V];
}

完整代码：

#include <bits/stdc++.h>
using namespace std;
int n, m;
const int N = 1010;
int dp[N];
int v[N], w[N];

int main() {
    scanf("%d%d", &m, &n);
    for (int i = 1; i <= n; i++)
        scanf("%d%d", &v[i], &w[i]);
        
    for (int i = 1; i <= n; i++) {
        for (int j = m; j >= v[i]; j--)
            dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
    } // 自我滚动数组
    
    printf("%d", dp[m]);
    return 0;
}

2 分组背包问题

问题描述

有 \(N\) 组物品和一个容量是 \(V\) 的背包。
每组物品有若干个，同一组内的物品最多只能选一个。
每件物品的体积是 \(v_{ik}\)，价值是 \(w_{ik}\)，其中 \(i\) 是组号，\(k\) 是组内编号。
求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。

输入描述：
第一行有两个整数 \(N,V\)，用空格隔开，分别表示物品组数和背包容量。
接下来有 \(N\) 组数据：

  • 每组数据第一行有一个整数 \(S_i\)，表示第 \(i\) 个物品组的物品数量；
  • 每组数据接下来有 \(S_i\) 行，每行有两个整数 \(v_{ik},w_{ik}\)，用空格隔开，分别表示第 \(i\) 个物品组的第 \(k\) 个物品的体积和价值。

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

分析

定义一个状态 \(dp[i][j]\)，表示把前 \(i\) 组的物品装进容量为 \(j\) 的背包（每个组里最多选一个物品）里可获得的最大价值。

状态转移方程：

\[dp[i][j]=\max\{dp[i-1][j],\ dp[i-1][j-v[i][k]]+w[i][k]\} \]

其中 \(dp[i-1][j]\) 表示第 \(i\) 组不选择物品，\(dp[i-1][j-v[i][k]]\) 表示第 \(i\) 组的第 \(k\) 个物品，求解方程需要 \(i,j,k\) 三重循环。

若改为滚动数组则状态转移方程为：

\[dp[j]=\max\{dp[j],\ dp[j-v[i][k]]+w[i][k]\} \]

参考代码

写法一

#include<bits/stdc++.h>
using namespace std;
const int N=110;
int n,m;
int dp[N],v[N],w[N];

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++)
    {
        int num; // 第i+1组的物品个数
        scanf("%d",&num);
        for(int j=1;j<=num;j++)
            scanf("%d%d",&v[j],&w[j]); // 第i组num个物品的体积和价格
            
        for(int j=m;j>=0;j--)
            for(int k=1;k<=num;k++)
                if(j>=v[k])
                    dp[j]=max(dp[j],dp[j-v[k]]+w[k]);
    }
    printf("%d",dp[m]);
    return 0;
}

写法二

#include<bits/stdc++.h>
using namespace std;
const int N=110;
int v[N][N],w[N][N],num[N];
// v[i][j]：第i组，第j个物品的体积
// w[i][j]：第i组，第j个物品的价值
// num[i]：第i组内物品个数
int dp[N];
int n,sum;

int main()
{
    cin>>n>>sum;
    for(int i=1;i<=n;i++)
    {
        cin>>num[i];
        for(int j=1;j<=num[i];j++)
            cin>>v[i][j]>>w[i][j];
    }
    
    for(int i=1;i<=n;i++)
        for(int j=sum;j>=0;j--)
            for(int k=0;k<=num[i];k++)
                if(j>=v[i][k])
                    dp[j]=max(dp[j],dp[j-v[i][k]]+w[i][k]);
                
    cout<<dp[sum];
    return 0;
}

3 多重背包问题

问题描述

有一个最大载重为 \(W\) 的采集车，洞穴里总共有 \(n\) 种宝物，每种宝物的价值为 \(v_i\)，重量为 \(w_i\)，每种宝物有 \(m_i\) 件。希望在采集车不超载的前提下，选择一些宝物装进采集车，使得它们的价值和最大。

输入描述：
第一行为一个整数 \(n\) 和 \(W\)，分别表示宝物种数和采集车的最大载重。
接下来 \(n\) 行每行三个整数 \(v_i,w_i,m_i\)。

输出描述：
输出最大宝物价值。

分析

将 \(m\) 件物品看成多个不同的物品，转化成 0/1 背包问题。

参考代码

基础暴力版本（三重循环，时间一般会爆掉）

#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int n, sum;   // n为物品种类数，sum为背包总体积
int dp[N], w[N], v[N], num[N];
// dp[i]：容量i的最大价值
// w[i]：第i个物品价值
// v[i]：第i个物品体积
// num[i]：第i个物品数量

int main() {
    cin >> n >> sum;
    for (int i = 1; i <= n; i++)
        cin >> v[i] >> w[i] >> num[i];
        
    for (int i = 1; i <= n; i++)
        for (int j = sum;j >=v[i]; j--)
            for (int k = 1;j >= k * v[i]&&k <= num[i]; k++)
                dp[j] = max(dp[j], dp[j - v[i] * k] + w[i] * k);
                
    cout << dp[sum];
    return 0;
}

二进制优化版本

数学规律：每个数都可以由以下部分来组成

\[num=a_n \cdot 2^n + a_{n-1} \cdot 2^{n-1} + \dots + a_1 \cdot 2 + a_0 \]

根据这个规律，任意一个数可从 \(1,2,4,8 \dots\) 以及一个多余项组成。
每个数都可由二次幂升序排列的数来组成，相比较 \(num\) 个数字，其二进制表示可以大大降低时间复杂度。
思路：把二次幂升序和多余项看成一种物品的选择，之后用 0/1 背包处理。

#include<bits/stdc++.h>
using namespace std;
const int N=11010,M=2010;
int dp[M];
int v[N],w[N];
int n,sum;

int main()
{
    cin>>n>>sum;
    int all=0;
    for(int i=1;i<=n;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        for(int k=1;k<=c;k*=2)
        {
            all++;
            v[all]=a*k;
            w[all]=b*k;
            c-=k;
        }
        if(c>0)
        {
            all++;
            v[all]=a*c;
            w[all]=b*c;
        }
    }
    n=all;
    for(int i=1;i<=n;i++)
        for(int j=sum;j>=v[i];j--)
            dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
            
    cout<<dp[sum];
    return 0;
}

4 完全背包问题

问题描述

现有 \(N\) 种物品和一个最多能承重 \(M\) 的背包，每种物品都有无限个，第 \(i\) 种物品的重量是 \(w_i\)，价值是 \(v_i\)。在背包能承受的范围内，试问将哪些物品装入背包后可使总价值最大，求这个最大价值。

分析

思路一（转化法）

把完全背包问题转化成多重背包问题，因为物品虽然是无限个，但能装进去的个数是有限多个。
将能装进 \(1\) 个、\(2\) 个、\(3\) 个 \(\dots\) 利用二进制优化来操作，最后变成 0/1 背包问题。
（个人结合二进制优化思路，非标准正解）

参考代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 1010, M = 11010;
int v[M], w[M];
int dp[N];
int n, sum;
int all;

int main() {
    cin >> n >> sum;
    for (int i = 1; i <= n; i++) {
        int t; // 最多能放多少东西
        int a, b; // a体积，b价值
        cin >> a >> b;
        t = sum / a;
        
        for (int k = 1; k <= t; k *= 2) { // 二进制优化
            all++;
            v[all] = a * k;
            w[all] = b * k;
            t -= k;
        }
        if (t > 0) { // 处理多余项
            all++;
            v[all] = a * t;
            w[all] = b * t;
        }
    }
    n = all;
    
    // 0/1背包
    for (int i = 1; i <= all; i++)
        for (int j = sum; j >= v[i]; j--)
            dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
            
    cout << dp[sum];
    return 0;
}

思路二（正解：状态方程优化）

观察规律：

\[\begin{aligned} dp[2][5]&=\max(dp[1][5],\ dp[1][3]+w,\ dp[1][1]+2w) \\ dp[2][3]&=\max(dp[1][3],\ dp[1][1]+w)=\max(dp[1][3],\ dp[2][1]+w) \\ dp[2][5]&=\max(dp[1][5],\ dp[2][3]+w) \end{aligned} \]

由此得到优化转移方程：

\[dp[i][j]=\max(dp[i-1][j],\ dp[i][j-v[i]]+w[i]) \]

其中 \(j\) 从小到大遍历。

参考代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int dp[N];
int v,w;
int n,sum;

int main()
{
    cin>>n>>sum;
    while(n--)
    {
        cin>>v>>w;
        for(int j=v;j<=sum;j++)
            dp[j]=max(dp[j],dp[j-v]+w);
    }
    cout<<dp[sum];
    return 0;
}

文章来源:https://www.cnblogs.com/XiaoRanMuQing/p/19813970
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系邮箱：jacktools123@163.com进行投诉反馈，一经查实，立即删除！

标签：

上一篇：包管理器用法速查
下一篇：2026年AI金融工具排行榜：深度测评7款工具后，发现真正的差距不在应用层

相关文章

最新发布

点击排行

本站推荐

标签云