1. Toy模板网首页
  2. > Toy博客

acwing算法基础之动态规划--背包问题

7月前 作者：YMWM_ 分类：Toy博客 阅读(36) 违法举报

这篇具有很好参考价值的文章主要介绍了acwing算法基础之动态规划--背包问题。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

1 基础知识

（零）
背包问题描述：有 N N N个物品，每个物品的体积是 v i v_i vi​，价值是 w i w_i wi​，现有容量是 V V V的背包，求这个背包能装下的物品的最大价值。

01背包问题：每个物品只有1个。
完全背包问题：每个物品有无穷多个。
多重背包问题：第 i i i个物品有 s i s_i si​个。
分组背包问题：有N组物品，每组有 s i s_i si​个物品，但只能选择其中一个。

（一）
01背包问题讲解。

状态定义f[i][j]：从前 i i i个物品中选择总体积不超过 j j j的物品的总价值的最大值。

状态转移：

  1. 不选择第 i i i个物品，即从前 i − 1 i-1 i−1个物品中选择总体积不超过 j j j的物品，根据状态的定义可知，为f[i-1][j]。
  2. 选择第 i i i个物品，即从前 i − 1 i-1 i−1个物品中选择总体积不超过 j − v [ i ] j-v[i] j−v[i]的物品，然后再加上w[i]，即f[i-1][j - v[i]] + w[i]。

f[i][j]的值取上述两者中的最大值即可。

初始化：f[0][0~V]=0。

最终答案：f[N][V]。

用代码表示如下，

#include <iostream>

using namespace std;

const int N = 1010;
int n, m;
int v[N];
int 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] << endl;
    
    return 0;
}

考虑到上述状态转移过程中，在计算第i层的状态时，只用到了第i-1层的信息，故可以使用滚动数组进行优化，将状态表示降成一维的。可以用一个临时数组来存取上一层的状态。更进一步，考虑f[i][j] = max(f[i][j], f[i-1][j - v[i]] + w[i])，发现计算f[i][j]时，需要知道f[i-1][j-v[i]]的信息，而我们可以从j=m到j=v[i]的顺序进行更新，那么使用的就是上一层的f[j-v[i]]，故省去了 O ( N ) O(N) O(N)的临时数组的空间。

C++代码如下，

#include <iostream>

using namespace std;

const int N = 1010;
int n, m;
int v[N];
int 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 = m; j >= v[i]; --j) {
            f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
    }
    
    cout << f[m] << endl;
    
    return 0;
}

（二）
完全背包问题讲解。

状态定义同上，即f[i][j]：从前 i i i个物品中选择总体积不超过 j j j的物品的总价值的最大值。

状态转移稍有不同，如下，

  1. 不选第 i i i个物品，即f[i-1][j]。
  2. 选1个第 i i i个物品，即f[i-1][j - v[i]] + w[i]。
  3. 选2个第 i i i个物品，即f[i-1][j - v[i] * 2] + w[i] * 2。
    ……
  4. 选 k k k个第 i i i个物品，即f[i-1][j - v[i] * k] + w[i] * k。

初始化：f[0][0~V]=0。

最终答案：f[N][V]。

C++代码如下，

#include <iostream>

using namespace std;

const int N = 1010;
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 k = 0; 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;
}

上述代码的三重循环可以优化到两重循环，考虑状态f[i][j]的求解，
f [ i ] [ j ] = m a x ( f [ i − 1 ] [ j ] ,                                                f [ i − 1 ] [ j − v [ i ] ] + w [ i ] ,                                                           f [ i − 1 ] [ j − v [ i ] ∗ 2 ] + w [ i ] ∗ 2 ,               ⋯   ,                                                           f [ i − 1 ] [ j − v [ i ] ∗ k ] + w [ i ] ∗ k ) f[i][j] = max(f[i-1][j], \\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ f[i-1][j -v[i]] + w[i], \\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ f[i-1][j - v[i] * 2] + w[i] * 2,\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \cdots,\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ f[i-1][j-v[i] * k] + w[i] * k) f[i][j]=max(f[i−1][j],                                              f[i−1][j−v[i]]+w[i],                                                         f[i−1][j−v[i]∗2]+w[i]∗2,             ⋯,                                                         f[i−1][j−v[i]∗k]+w[i]∗k)
考虑状态f[i][j - v[i]]的求解，
f [ i ] [ j − v [ i ] ] = m a x ( f [ i − 1 ] [ j − v [ i ] ] ,                                                      f [ i − 1 ] [ j − v [ i ] ∗ 2 ] + w [ i ] ,                                                            f [ i − 1 ] [ j − v [ i ] ∗ 3 ] + w [ i ] ∗ 2 ,                ⋯   ,                                                            f [ i − 1 ] [ j − v [ i ] ∗ k ] + w [ i ] ∗ k ) f[i][j - v[i]] = max(f[i-1][j- v[i]], \\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ f[i-1][j -v[i] * 2] + w[i], \\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ f[i-1][j - v[i] * 3] + w[i] * 2,\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \cdots,\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ f[i-1][j-v[i] * k] + w[i] * k) f[i][j−v[i]]=max(f[i−1][j−v[i]],                                                    f[i−1][j−v[i]∗2]+w[i],                                                          f[i−1][j−v[i]∗3]+w[i]∗2,              ⋯,                                                          f[i−1][j−v[i]∗k]+w[i]∗k)
观察上式，发现有，
f [ i ] [ j ] = m a x ( f [ i − 1 ] [ j ] ,                                          f [ i ] [ j − v [ i ] ] + w [ i ] ) f[i][j] = max(f[i-1][j], \\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ f[i][j-v[i]] + w[i]) f[i][j]=max(f[i−1][j],                                        f[i][j−v[i]]+w[i])
故写成代码如下，

#include <iostream>

using namespace std;

const int N = 1010;
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][j - v[i]] + w[i]);
        }
    }
    
    cout << f[n][m] << endl;
    
    return 0;
}

更进一步，可以利用滚动数组进行优化，考虑状态f[i][j]的计算公式f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i])，由于此处使用的是第i层的j-v[i]，故无需将j从j=m到j=v[i]这样倒序遍历，正序遍历即可。

C++代码如下，

#include <iostream>

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 = 0; j <= m; ++j) {
            if (j >= v[i]) f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
    }
    
    cout << f[m] << endl;
    
    return 0;
}

（三）
多重背包问题讲解。

状态定义同（一），即f[i][j]：使用前 i i i个物体且总体积不超过 j j j，总价值的最大值。
状态转移：

  1. 不选择第 i i i个物品，即f[i-1][j]。
  2. 选择1个第 i i i个物品，即f[i-1][j-v[i]] + w[i]。
  3. 选择2个第 i i i个物品，即f[i-1][j-v[i]*2] + w[i]*2
    ……
  4. 选择s[i]个第 i i i个物品，即f[i-1][j-v[i]*s[i]] + w[i] * s[i]。

C++代码如下，

#include <iostream>

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 * v[i] <= j && k <= s[i]; ++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;
}

上述时间复杂度为 O ( n ⋅ m ⋅ s ) O(n\cdot m\cdot s) O(n⋅m⋅s)，可以优化到 O ( n ⋅ m ⋅ l o g ( s ) ) O(n\cdot m \cdot log(s)) O(n⋅m⋅log(s))。

具体介绍如下，考虑到有s[i]个第 i i i类物品，可以将其拆成 l o g ( s [ i ] ) log(s[i]) log(s[i])个，比如有20个第 i i i类物品，可以拆成1个、2个、4个、8个和5个。然后转换成01背包问题。

C++代码如下，

#include <iostream>

using namespace std;

const int N = 25000, M = 2010;
int n, m, cnt;
int v[N], w[N];
int f[M];

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        int a, b, c;
        cin >> a >> b >> c;//体积a，价值b，个数c
        
        int k = 1;
        while (c >= k) {
            cnt ++;
            v[cnt] = k * a;
            w[cnt] = k * b;
            c -= k;
            k <<= 1;
        }
        
        if (c > 0) {
            cnt++;
            v[cnt] = c * a;
            w[cnt] = c * b;
        }
    }
    
    //做一遍01背包问题
    for (int i = 1; i <= cnt; ++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 N N组物品，每组物品有 s i s_i si​类，每一类只有一个，分别有体积 v i v_i vi​、价值 w i w_i wi​，现在有体积为 V V V的背包，只能从每组物品中挑选一个或者不选，求背包的最大价值。

状态定义基本同（一），即f[i][j]：从前 i i i个物品中选择总体积不超过 j j j的，其最大价值。

状态转移，有：

  1. 不选择第 i i i组物品，f[i-1][j]。
  2. 选择第 i i i组物品中的第0个，即f[i-1][j - v[i][0]] + w[i][0]。
  3. 选择第 i i i组物品中的第1个，即f[i-1][j - v[i][1]] + w[i][1]。
    ……
  4. 选择第 i i i组物品中的第k个，即f[i-1][j - v[i][k]] + w[i][k]。

C++代码如下，

#include <iostream>

using namespace std;

const int N = 110;
int n, m;
int s[N];
int v[N][N], w[N][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;
}

2 模板

暂无。。。文章来源地址https://www.toymoban.com/news/detail-752581.html

3 工程化

暂无。。。

到了这里，关于acwing算法基础之动态规划--背包问题的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • acwing算法基础之动态规划--DP习题课1

    暂无。。。 暂无。。。 题目1 ：最长严格上升子序列，要求时间复杂度为 O ( n l o g n ) O(nlogn) O ( n l o g n ) 。 解题思路：保存每个长度下的最小的结尾元素值，遍历数组元素时，通过二分找到它，然后更新它即可，返回len。 该算法的关键步骤如下： 定义向量 vec ， vec[i] 表示

    2024年02月03日
    浏览(38)
  • 【AcWing算法基础课】第五章 动态规划（未完待续）

    【AcWing算法基础课】第五章 动态规划（未完待续）

    本专栏文章为本人AcWing算法基础课的学习笔记，课程地址在这。如有侵权，立即删除。 dp问题的优化 ：在基本形式dp上作等价变形。 dp问题的解题方法 ： 1）状态表示 集合 属性：最大值/最小值/数量。 2）状态计算 集合划分（不重不漏） 题目链接： 2. 01背包问题 - AcWing题库

    2024年02月12日
    浏览(34)

  • acwing算法基础之动态规划--线性DP和区间DP

    线性DP：状态转移表达式存在明显的线性关系。 区间DP：与顺序有关，状态与区间有关。 题目1 ：数字三角形。 解题思路：直接DP即可， f[i][j] 可以来自 f[i-1][j] + a[i][j] 和 f[i-1][j-1] + a[i][j] ，注意 f[i-1][j] 不存在的情况（最后一个点）和 f[i-1][j-1] 不存在的情况（第一个点）。

    2024年02月04日
    浏览(40)
  • acwing算法基础之动态规划--数位统计DP、状态压缩DP、树形DP和记忆化搜索

    acwing算法基础之动态规划--数位统计DP、状态压缩DP、树形DP和记忆化搜索

    暂无。。。 暂无。。。 题目1 ：求a~b中数字0、数字1、…、数字9出现的次数。 思路：先计算1~a中每位数字出现的次数，然后计算1~b-1中每位数字出现的次数，两个相减即是最终答案。 那么，如何计算1~a中每位数字出现的次数呢？ 首先，将a的每一位存入向量num中，例如a=123

    2024年02月04日
    浏览(37)
  • AcWing算法提高课-1.3.11二维费用的背包问题

    AcWing算法提高课-1.3.11二维费用的背包问题

    点这里 题目描述 有 N N N 件物品和一个容量是 V V V 的背包，背包能承受的最大重量是 M M M 。 每件物品只能用一次。体积是 v i v_i v i ​ ，重量是 m i m_i m i ​ ，价值是 w i w_i w i ​ 。 求解将哪些物品装入背包，可使物品总体积不超过背包容量，总重量不超过背包可承受的最大

    2024年02月06日
    浏览(36)

  • C++算法之动态规划(ACWING题目）

    动态规划时间复杂度：状态数量*转移计算量 线性DP 一.数字三角形 动态规划：     1.状态表示：         集合：f[i, j]表示所有从起点走到(i, j)的路径         属性：所有路径上的数字之和的最大值     2.状态计算：         如何得到f[i, j]?             从左边路径走到和

    2024年02月20日
    浏览(32)
  • 算法学习17-动态规划01：背包问题

    算法学习17-动态规划01：背包问题

    提示：以下是本篇文章正文内容： 提示：这里对文章进行总结： 💕💕💕

    2024年04月27日
    浏览(33)

  • Python 算法基础篇：背包问题的动态规划解法

    背包问题是计算机科学中一个重要的组合优化问题，动态规划是解决该问题的高效算法技术。本篇博客将重点介绍背包问题的动态规划解法，包括状

    2024年02月16日
    浏览(30)

  • 算法基础复盘笔记Day09【动态规划】—— 背包问题

    ❤ 作者主页：欢迎来到我的技术博客😎 ❀ 个人介绍：大家好，本人热衷于 Java后端开发 ，欢迎来交流学习哦！(￣▽￣)~* 🍊 如果文章对您有帮助，记得 关注 、 点赞 、 收藏 、 评论 ⭐️⭐️⭐️ 📣 您的支持将是我创作的动力，让我们一起加油进步吧！！！🎉🎉 1. 题目

    2023年04月22日
    浏览(34)
  • Acwing.901 滑雪(动态规划)

    Acwing.901 滑雪(动态规划)

    给定一个R行C列的矩阵，表示一个矩形网格滑雪场。 矩阵中第i行第j列的点表示滑雪场的第i行第j列区域的高度。 一个人从滑雪场中的某个区域内出发，每次可以向上下左右任意一个方向滑动一个单位距离。当然，一个人能够滑动到某相邻区域的前提是该区域的高度低于自己

    2024年02月15日
    浏览(38)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包