完全背包总结

素颜马尾好姑娘i 2024-03-26 17:57 47阅读 0赞

## 1.组合数和排列数 ##

对于01背包来说，并不区分内外层的遍历顺序，而对于完全背包来说，如果外层是背包容量，则球的是排列数，如果外层是物品数，则求的是组合数。同时间注意对于求方案总数的形式，我们可以采取dp\[i\] += dp\[i - w\[i\]\] 的形式。

## 2.完全背包数学推导 ##

[【动态规划/背包问题】从数学角度推导「完全背包」与「01 背包」之间的遍历顺序关系][01]

![2815add12526923c30217095c2970f5d.png][]

![07239e80e44946d8b1de733bedf3701d.png][]

对于遇到的完全背包问题我们不必再推导数学公式，而是直接采用这个公式去套用即可。一维的完全背包是比二维的完全背包要节省时间的。

class Solution {
        public int maxValue(int N, int C, int[] v, int[] w) {
            int[] dp = new int[C + 1];
            for (int i = 0; i < N; i++) {
                for (int j = 0; j <= C; j++) {
                    // 不考虑第 i 件物品的情况（选择 0 件物品 i）
                    int n = dp[j];
                    // 考虑第 i 件物品的情况
                    int y = j - v[i] >= 0 ? dp[j - v[i]] + w[i] : 0; 
                    dp[j] = Math.max(n, y);
                }
            }
            return dp[C];
        }
    }

[01]: https://mp.weixin.qq.com/s?__biz=MzU4NDE3MTEyMA==&mid=2247486107&idx=1&sn=e5fa523008fc5588737b7ed801caf4c3&chksm=fd9ca184caeb28926959c0987208a3932ed9c965267ed366b5b82a6fc16d42f1ff40c29db5f1&scene=178&cur_album_id=1751702161341628417#rd
[2815add12526923c30217095c2970f5d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/fe0697997e694462978c76cd265d1a92.png
[07239e80e44946d8b1de733bedf3701d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/0dd594251c7541a8811f78075a1ab837.png

发表评论取消回复

表情：

评论列表（有 0 条评论，47人围观）

还没有评论，来说两句吧...

相关阅读

相关完全背包总结

1.组合数和排列数对于01背包来说，并不区分内外层的遍历顺序，而对于完全背包来说，如果外层是背包容量，则球的是排列数，如果外层是物品数，则求的是组合数。同时间注意对于求

素颜马尾好姑娘i/ 2024年03月26日 17:57/ 0 赞/ 48 阅读

相关背包DP | 完全背包问题

> 完全背包问题：有n种物品，每一件的物品重量为 w\[ i \]，价值为 c\[ i \]。现有一个容量为V的背包 (背包的最大承重为V)，问如何选取物品放入背包，使得背包内

小灰灰/ 2023年07月19日 10:34/ 0 赞/ 11 阅读

相关完全背包

完全背包在背包九讲中有很详细的讲解，但是今天碰到题尝试了一下他给的算法，发现并不快，看了一下其他的代码，速度很快！题目链接http://hihocoder.com/prob

拼搏现实的明天。/ 2022年08月21日 02:16/ 0 赞/ 179 阅读

相关完全背包问题

1. 问题描述有 N 种物品, 物品 i 的重量为 wi, 价格为 vi, 背包所能承受的最大重量为 W。其中, N,W,wi,vi≥0 若每种物品仅有一件,

短命女/ 2022年07月12日 06:37/ 0 赞/ 200 阅读

相关 01背包,完全背包

01背包问题：一个背包总容量为V，现在有N个物品，第i个物品体积为weight\[i\]，价值为value\[i\]，现在往背包里面装东西，怎么装能使背包的内物品价值最大？

男娘i/ 2022年06月09日 04:16/ 0 赞/ 230 阅读

相关完全背包

完全背包和01背包的区别 > 01背包：有n个物品，每种物品只能被使用一次 > > 完全背包：有n个物品，每个物品可以被多次使用完全背包的递推公式可以由01背包的递推公

ゞ浴缸里的玫瑰/ 2022年06月08日 09:43/ 0 赞/ 177 阅读

相关完全背包

问题：有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的费用是c\[i\]，价值是w\[i\]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量

今天药忘吃喽~/ 2022年05月31日 01:05/ 0 赞/ 191 阅读

相关背包问题—01背包、完全背包

01背包问题题目有m件物品和一个容量为V 的背包。放入第i 件物品占用的体积是Vi，得到的价值是Wi。求解将哪些物品装入背包可使价值总和最大。思路这

末蓝、/ 2022年05月30日 10:10/ 0 赞/ 348 阅读

相关 0-1背包&完全背包

First：0-1背包问题 1.定义define：所谓的0-1背包就是指每种物品只有一件，而每件物品只有两种选择，即选择放或是不放 2.问题：一个小偷来出来活动

桃扇骨/ 2022年05月28日 12:24/ 0 赞/ 178 阅读

相关背包问题-01背包，完全背包，多重背包

背包问题-01背包，完全背包，多重背包 -------------------- 01背包：概念：有Goods\_Num件物品，MAX\_V

太过爱你忘了你带给我的痛/ 2022年05月14日 09:23/ 0 赞/ 286 阅读