完全背包总结 素颜马尾好姑娘i 2024-03-26 17:57 8阅读 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
还没有评论,来说两句吧...