【动态规划之完全背包问题】完全背包问题的通用解法与优化

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

⭐️前面的话⭐️

本篇文章将介绍动态规划中的背包问题——完全背包问题,前面我们已经介绍了0-1背包问题,其实完全背包问题就只改了0-1背包问题的一个条件,即物品可选择次数由一次改为无数次,仅此而已,下面我们就来开始介绍完全背包问题。

📒博客主页:未见花闻的博客主页
🎉欢迎关注🔎点赞👍收藏⭐️留言📝
📌本文由未见花闻原创!
📆首发时间:🌴2022年10月22日🌴
✉️坚持和努力一定能换来诗与远方!
💭推荐书籍:📚《算法》,📚《算法导论》
💬参考在线编程网站:🌐牛客网🌐力扣
博主的码云gitee,平常博主写的程序代码都在里面。
博主的github,平常博主写的程序代码都在里面。
🍭作者水平很有限,如果发现错误,一定要及时告知作者哦!感谢感谢!



【动态规划之完全背包问题】完全背包问题的通用解法与优化


⭐️【问题导入】完全背包原题⭐️

🔐题目详情

N N N 种物品和一个容量为 C C C 的背包,每种物品都有无限件

i i i 件物品的体积是 v [ i ] v[i] v[i] ,价值是 w [ i ] w[i] w[i]

求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。

其实就是在 0-1 背包问题的基础上,增加了每件物品可以选择多次的特点(在容量允许的情况下)。

示例 :

输入: N = 2, C = 5, v = [1,2], w = [1,2]
输出: 5
解释: 选一件物品 1,再选两件物品 2,可使价值最大。

💡解题思路与代码

🍭朴素解法

我们可以直接将0-1背包的状态定义直接拿来使用:

状态定义: 不妨定义 f [ i ] [ j ] f[i][j] f[i][j]表示从前 i i i件物品中选择,容量不超过 j j j的最大价值。

确定初始状态: 当只有一种物品选择时,由于数量是无限的,所以尽量地选就行,不要超过容量 j j j,不妨设选这一种物品的最大件数为 k k k,则有 f [ 0 ] [ j ] = k × w [ i ] , 其中 k × v [ i ] < = j f[0][j]=k \times w[i],其中k\times v[i]<=j f[0][j]=k×w[i],其中k×v[i]<=j

状态转移方程推导: 当我们选择第 i i i件物品的时候,我们可以选择 0 , 1 , 2... k 0,1,2...k 0,1,2...k件,其中 k k k是最大能够选择的件数,即在不超过容量 j j j的情况下。

当我们不选择第 i i i件物品时,即 k = 0 k=0 k=0 f [ i ] [ j ] = f [ i − 1 ] [ j ] f[i][j]=f[i-1][j] f[i][j]=f[i1][j]
当我们选择 1 1 1 i i i件物品时,即 k = 1 k=1 k=1 f [ i ] [ j ] = f [ i − 1 ] [ j − v [ i ] ] + w [ i ] f[i][j]=f[i-1][j - v[i]] + w[i] f[i][j]=f[i1][jv[i]]+w[i]
当我们选择 2 2 2 i i i件物品时,即 k = 2 k=2 k=2 f [ i ] [ j ] = f [ i − 1 ] [ j − 2 ∗ v [ i ] ] + 2 ∗ w [ i ] f[i][j]=f[i-1][j - 2 * v[i]] + 2*w[i] f[i][j]=f[i1][j2v[i]]+2w[i]

当我们选择 k k k i i i件物品时,即 k = k k=k k=k f [ i ] [ j ] = f [ i − 1 ] [ j − k ∗ v [ i ] ] + k ∗ w [ i ] f[i][j]=f[i-1][j - k * v[i]]+k*w[i] f[i][j]=f[i1][jkv[i]]+kw[i]

我们所要求的是最大的价值,所以取以上所有情况的最大值即可。

综上所述,我们的状态转移方程就出来了,不妨记当前物品的价值为:

f [ i ] [ j ] = m a x ( f [ i − 1 ] [ j − k ∗ v [ i ] ] + k ∗ w [ i ] ) , k = 0 , 1 , . . . f[i][j]=max(f[i-1][j-k*v[i]]+k*w[i]),k=0,1,... f[i][j]=max(f[i1][jkv[i]]+kw[i]),k=0,1,...

实现代码:

    /**
     *
     * @param n 物品个数
     * @param c 背包的总容量
     * @param w 每种物品的价值
     * @param v 每种物品的容量
     * @return 能将物品放进背包的最大价值
     */
    public int cknapsack1(int n, int c, int[] w, int[] v) {
        //状态定义f[i][j]表示最大价值
        int[][] f = new int[n][c + 1];
        //确定初始状态
        for (int j = 1; j <= c; j++) {
            int k = j / v[0];
            f[0][j] = k * w[0];
        }
        //状态转移f[i][j]=max(f[i-1][j - k * v[i]]+k*w[i]
        for (int i = 1; i < n; i++) {
            int val = w[i];
            for (int j = 1; j <= c; j++) {
                int cur = 0;
                for (int k = 0; j >= k * v[i]; k++) {
                    int t = f[i - 1][j - k * v[i]] + k * val;
                    cur = Math.max(t, cur);
                }
                f[i][j] = cur;
            }
        }
        return f[n - 1][c];
    }

时间复杂度: O ( n ∗ c ∗ k ) O(n*c*k) O(nck) k k k的值不会大于 c c c,因为最低物品价值为 1 1 1,最多选择的件数不会超过 c c c
空间复杂度: O ( n ∗ c ) O(n*c) O(nc)

🍭滚动数组优化空间

根据观察我们知道第 i i i行的状态仅依赖与第 i − 1 i-1 i1行的状态,因此我们可以使用滚动数组进行优化。

实现代码:

    /**
     *
     * @param n 物品个数
     * @param c 背包的总容量
     * @param w 每种物品的价值
     * @param v 每种物品的容量
     * @return 能将物品放进背包的最大价值
     */
    public int cknapsack2(int n, int c, int[] w, int[] v) {
        //状态定义f[i][j]表示最大价值 滚动数组优化
        int[][] f = new int[2][c + 1];
        //确定初始状态
        for (int j = 1; j <= c; j++) {
            int k = j / v[0];
            f[0][j] = k * w[0];
        }
        //状态转移f[i][j]=max(f[i-1][j - k * v[i]]+k*w[i]
        for (int i = 1; i < n; i++) {
            int val = w[i];
            int ci = i & 1;
            int pi = (i - 1) & 1;
            for (int j = 1; j <= c; j++) {
                int cur = 0;
                for (int k = 0; j >= k * v[i]; k++) {
                    int t = f[pi][j - k * v[i]] + k * val;
                    cur = Math.max(t, cur);
                }
                f[ci][j] = cur;
            }
        }
        return f[(n - 1) & 1][c];
    }

对于时空复杂度,只是优化了空间而已,所以时间复杂度不发生改变,空间复杂度优化到 O ( c ) O(c) O(c)
时间复杂度: O ( n ∗ c ∗ k ) O(n*c*k) O(nck) k k k的值不会大于 c c c,因为最低物品价值为 1 1 1,最多选择的件数不会超过 c c c
空间复杂度: O ( c ) O(c) O(c)

🍭一维数组优化空间

首先我们对状态转移方程进行一个简单的推导:

f [ i ] [ j ] = m a x ( f [ i − 1 ] [ j ] , f [ i − 1 ] [ j − v [ i ] ] + w [ i ] , f [ i − 1 ] [ j − 2 ∗ v [ i ] ] + 2 ∗ w [ i ] , . . . , f [ i − 1 ] [ j − k ∗ v [ i ] ] + k ∗ w [ i ] ) f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i],f[i-1][j-2*v[i]]+2*w[i],...,f[i-1][j-k*v[i]]+k*w[i]) f[i][j]=max(f[i1][j],f[i1][jv[i]]+w[i],f[i1][j2v[i]]+2w[i],...,f[i1][jkv[i]]+kw[i])

f [ i ] [ j − v [ i ] ] = m a x ( f [ i − 1 ] [ j − v [ i ] ] , f [ i − 1 ] [ j − 2 ∗ v [ i ] ] + w [ i ] , f [ i − 1 ] [ j − 3 ∗ v [ i ] ] + 2 ∗ w [ i ] . . . , f [ i − 1 ] [ j − k ∗ v [ i ] ] + ( k − 1 ) ∗ w [ i ] ) f[i][j-v[i]]=max(f[i-1][j-v[i]],f[i-1][j-2*v[i]]+w[i],f[i-1][j-3*v[i]]+2*w[i]...,f[i-1][j-k*v[i]]+(k-1)*w[i]) f[i][jv[i]]=max(f[i1][jv[i]],f[i1][j2v[i]]+w[i],f[i1][j3v[i]]+2w[i]...,f[i1][jkv[i]]+(k1)w[i])

其中 k ∗ v [ i ] < = j k*v[i]<=j kv[i]<=j

通过观察上面两个状态的式子,我们发现后面一部分式子是差了一个 w [ i ] w[i] w[i]如下图:

【动态规划之完全背包问题】完全背包问题的通用解法与优化

所以我们可以进一步优化状态转移方程,即:

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[i1][j],f[i][jv[i]]+w[i])

对于新推导出来的状态转移方程,它的状态转移仅仅只依赖与上一行同列状态与同一行元素前面的元素,所以我们可以将原来的二维数组优化为一维,由于它只依赖左边与正上方的元素,我们可以采取从小到大遍历背包容量状态来求背包中所放物品最大值。

【动态规划之完全背包问题】完全背包问题的通用解法与优化

只保留【背包容量】维度,状态转移方程为:

f [ j ] = m a x ( f [ j ] , f [ j − v [ i ] ] + w [ i ] ) f[j]=max(f[j],f[j-v[i]]+w[i]) f[j]=max(f[j],f[jv[i]]+w[i])

实现代码:

    /**
     *
     * @param n 物品个数
     * @param c 背包的总容量
     * @param w 每种物品的价值
     * @param v 每种物品的容量
     * @return 能将物品放进背包的最大价值
     */
    public int cknapsack3(int n, int c, int[] w, int[] v) {
        //状态定义f[i][j]表示最大价值 一维数组优化
        int[] f = new int[c + 1];
        //确定初始状态f[0]=0
        //状态转移
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= c; j++) {
                //不选择物品
                int nopt = f[j];
                //选择物品
                int opt = j >= v[i] ? f[j - v[i]] + w[i] : nopt;

                f[j] = Math.max(opt, nopt);
            }
        }
        return f[c];
    }

时间复杂度: O ( n ∗ c ) O(n*c) O(nc)
空间复杂度: O ( c + 1 ) O(c+1) O(c+1)

🌱总结

以上我们介绍了【完全背包问题】的朴素解法和优化方案,其中一维优化是最复杂的,因为使用了一些数学上的推导,比较抽象,不是特别容易理解,我建议自己尝试推导一遍,这样能够更快的理解并且更深刻。
相比于0-1背包问题的优化,形式上,我们只需要将 01 背包问题的「一维空间优化」解法中的「容量维度」遍历方向从「从大到小 改为 从小到大」就可以解决完全背包问题。
但本质是因为两者进行状态转移时依赖了不同的格子:
0 -1 背包依赖的是「上一行正上方的格子」和「上一行左边的格子」。
完全背包依赖的是「上一行正上方的格子」和「本行左边的格子」。


觉得文章写得不错的老铁们,点赞评论关注走一波!谢谢啦!

【动态规划之完全背包问题】完全背包问题的通用解法与优化文章来源地址https://www.toymoban.com/news/detail-420853.html

到了这里,关于【动态规划之完全背包问题】完全背包问题的通用解法与优化的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

领支付宝红包 赞助服务器费用

相关文章

  • 动态规划-背包问题-完全背包

    对比01背包,完全背包中的每件物品有无数件。 也就是说,每件物品可以拿0,1,…,k,…件。 dp[i][j]表示前i种物品,体积为j时的最大价值 对于第i件物品: 不拿:dp[i][j]⇐dp[i-1][j] 拿一件:dp[i][j]⇐dp[i-1][j-w[i]]+v[i] 拿两件:dp[i][j]⇐dp[i-1][j-2w[i]]+2v[i] … 拿k件:dp[i]][j]⇐dp[i

    2024年04月08日
    浏览(46)
  • 完全背包&多重背包问题(动态规划)

    完全背包问题: 每个物品使用次数没有限制,与0-1背包的不同之处在于 遍历背包的顺序 是正序。 多重背包问题: 与完全背包的区别在于,每一种物品是有个数限制的,不能无限选择。这篇博客讲解的非常详细,可以参考学习: 多重背包问题---超详细讲解+优化(不懂你揍我

    2024年04月10日
    浏览(45)
  • 动态规划之背包问题——完全背包

    算法相关数据结构总结: 序号 数据结构 文章 1 动态规划 动态规划之背包问题——01背包 动态规划之背包问题——完全背包 动态规划之打家劫舍系列问题 动态规划之股票买卖系列问题 动态规划之子序列问题 算法(Java)——动态规划 2 数组 算法分析之数组问题 3 链表 算法

    2024年02月03日
    浏览(53)
  • Python 算法基础篇:背包问题的动态规划解法

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

    2024年02月16日
    浏览(39)
  • 动态规划:完全背包问题

    ACwing #3. 完全背包问题 完全背包问题和01背包问题很相似。 01背包问题每个物品只能选一个,而完全背包问题每个物品可以选无限次。 DP问题的关键是找到状态转移方程: ①定义f[i][j]表示从前 i 个物品中选择,体积为 j 的时候的最大价值。 ②那么转移方程f[i][j] = max(f[i - 1][j

    2023年04月19日
    浏览(42)
  • 动态规划——完全背包问题

    由于本人实力尚浅,接触算法没多久,写这篇blog仅仅是想要提升自己对算法的理解,如果各位读者发现什么错误,恳请指正,希望和大家一起进步。(●’◡’●) 了解完全背包问题前可以先去看看01背包问题(良心正解),先了解这个基础问题会更有利于你了解下面的完全背

    2024年02月04日
    浏览(45)
  • 算法系列--动态规划--背包问题(3)--完全背包介绍

    💕\\\"Su7\\\"💕 作者:Lvzi 文章主要内容:算法系列–动态规划–背包问题(3)–完全背包介绍 大家好,今天为大家带来的是 算法系列--动态规划--背包问题(3)--完全背包介绍 链接: 完全背包 可以发现完全背包问题和01背包问题还是特比相似的 分析: 完全背包问题 是 01背包问题 的推广

    2024年04月25日
    浏览(41)
  • 动态规划完全背包问题-java

    完全背包问题跟01背包问题思路大致一样,只不过对于物品的拿取次数不在限制,我们只需要考虑这点即可。 文章目录 前言 一、什么是完全背包问题? 二、问题模拟 1.样例数据 2.算法思路 三、代码如下 1.代码如下(示例): 2.读入数 3.代码运行结果 总结 完全背包问题跟

    2024年04月26日
    浏览(42)
  • 动态规划-----背包类问题(0-1背包与完全背包)详解

    目录 什么是背包问题? 动态规划问题的一般解决办法: 0-1背包问题: 0 - 1背包类问题  分割等和子集:  完全背包问题:  完全背包类问题 零钱兑换II: 背包问题(Knapsack problem)是一种组合优化的NP完全问题。 问题可以描述为:给定一组物品,每种物品都有自己的重量和价格

    2024年04月17日
    浏览(33)
  • 力扣刷题-动态规划算法3:完全背包问题

    问题描述: 1)有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i],得到的价值是value[i] 。 2) 每件物品都有无限个(也就是可以放入背包多次) (比0-1背包多出的条件) 3) 求解将哪些物品装入背包里物品价值总和最大。 求解步骤: 1)首先遍历物品,然

    2023年04月13日
    浏览(53)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包