动态规划专题讲解(二)

简介: 动态规划专题讲解(二)


多重背包


LeetCode上无对应题目,只简单介绍


1. 多重背包例题

题目

有N种物品和一个容量为 V  的背包。第i种物品最多有 M i 件可用,每件耗费的空间是C i

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


多重背包和01背包是非常像的, 为什么和01背包像呢?


每件物品最多有 M i件可用,把 M i 件摊开,其实就是一个01背包问题了。


例如:


背包最大重量为10。


物品为:


重量 价值 数量
物品0

1

15

2

物品1

3

20

3

物品2

4

30

2

问背包能背的物品最大价值是多少?


和如下情况有区别么?


重量 价值 数量
物品0

1

15

1

物品0

1

15

1

物品1

3

20

1

物品1

3

20

1

物品1

3

20

1

物品2

4

30

1

物品2

4

30

1

毫无区别,这就转成了一个01背包问题了,且每个物品只用一次。


思路

将有多件的物品展开,就可将完全背包转换成01背包


代码展示

#include 
#include 
using namespace std;
void test_multi_pack()
{
    vector weight = {1, 3, 4};
    vector value = {15, 20, 30};
    vector nums = {2, 3, 2};
    int bagWeight = 10;
    for (int i = 0; i < nums.size(); i++)
    {
        while (nums[i] > 1)
        { // nums[i]保留到1,把其他物品都展开
            weight.push_back(weight[i]);
            value.push_back(value[i]);
            nums[i]--;
        }
    }
    vector dp(bagWeight + 1, 0);
    for (int i = 0; i < weight.size(); i++)
    { // 遍历物品
        for (int j = bagWeight; j >= weight[i]; j--)
        { // 遍历背包容量
            dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
        }
        for (int j = 0; j <= bagWeight; j++)
        {
            cout << dp[j] << " ";
        }
        cout << endl;
    }
    cout << dp[bagWeight] << endl;
}
int main()
{
    test_multi_pack();
    return 0;
}


小结

做了这些题目后,感觉在没有系统学习dp之前,抓不住重点,有时稀里糊涂ac了,但不能完整推出来。所以说,卡尔哥的专题真的很有帮助!


四、打家劫舍


打家劫舍(LeetCode-198)

题目

你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。


给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。


示例 1:

输入:[1,2,3,1]
输出:4
解释:偷窃 1 号房屋 (金额 = 1) ,然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。


示例 2:

输入:[2,7,9,3,1]
输出:12
解释:偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9),接着偷窃 5 号房屋 (金额 = 1)。
     偷窃到的最高金额 = 2 + 9 + 1 = 12 。


提示:


1 <= nums.length <= 100

0 <= nums[i] <= 400

思路

五部曲


dp[i]含义


偷窃前 i 个房子(包括房子i)可以获取的最大金额

递推公式


d p [ i ] = m a x ( d p [ i − 1 ] , d p [ i − 2 ] + n u m s [ i ] )

数组初始化


dp[0]=0 dp[1]=nums[0]

遍历顺序


从前往后

代码

class Solution
{
public:
    int rob(vector &nums)
    {
        int n = nums.size();
        if (n == 1)
        {
            return nums[0];
        }
        if (n == 2)
        {
            return max(nums[0], nums[1]);
        }
        vector dp(2);
        dp[0] = nums[0];
        dp[1] = max(nums[0], nums[1]);
        int result;
        for (int i = 2; i < n; i++)
        {
            result = max(dp[1], dp[0] + nums[i]);
            dp[0] = dp[1];
            dp[1] = result;
        }
        return result;
    }
};


打家劫舍Ⅱ(LeetCode-213)

题目

你是一个专业的小偷,计划偷窃沿街的房屋,每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ,这意味着第一个房屋和最后一个房屋是紧挨着的。同时,相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警 。


给定一个代表每个房屋存放金额的非负整数数组,计算你 在不触动警报装置的情况下 ,今晚能够偷窃到的最高金额。


示例 1:

输入:nums = [2,3,2]
输出:3
解释:你不能先偷窃 1 号房屋(金额 = 2),然后偷窃 3 号房屋(金额 = 2), 因为他们是相邻的。


示例 2:

输入:nums = [1,2,3,1]
输出:4
解释:你可以先偷窃 1 号房屋(金额 = 1),然后偷窃 3 号房屋(金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。


示例 3:

输入:nums = [1,2,3]
输出:3


提示:


1 <= nums.length <= 100

0 <= nums[i] <= 1000

思路

当房间数不超过二,不需要考虑首尾


超过二时,因为不能同时偷首尾房间,所以可以分两种情况考虑


不偷最后一间情况:盗窃范围 n u m s [ 0 : n − 2 ]

不偷第一间情况:盗窃范围 n u m s [ 1 : n − 1 ]

二者取较大值


代码展示

class Solution
{
public:
    int rob(vector &nums)
    {
        int n = nums.size();
        if (n == 1)
        {
            return nums[0];
        }
        int left = robRange(nums, 0, n - 2);
        int right = robRange(nums, 1, n - 1);
        return max(left, right);
    }
    int robRange(vector &nums, int start, int end)
    {
        if (start == end)
        {
            return nums[start];
        }
        vector dp(nums.size());
        dp[start] = nums[start];
        dp[start + 1] = max(nums[start], nums[start + 1]);
        for (int i = start + 2; i <= end; i++)
        {
            dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);
        }
        return dp[end];
    }
};


打家劫舍Ⅲ(LeetCode-337)

题目

小偷又发现了一个新的可行窃的地区。这个地区只有一个入口,我们称之为 root 。


除了 root 之外,每栋房子有且只有一个“父“房子与之相连。一番侦察之后,聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ,房屋将自动报警。


给定二叉树的 root 。返回 在不触动警报的情况下 ,小偷能够盗取的最高金额 。


示例 1:


输入: root = [3,2,3,null,3,null,1]
输出: 7 
解释: 小偷一晚能够盗取的最高金额 3 + 3 + 1 = 7


示例 2:


输入: root = [3,4,5,1,3,null,1]
输出: 9
解释: 小偷一晚能够盗取的最高金额 4 + 5 = 9


提示:


树的节点数在 [1, 104] 范围内

0 <= Node.val <= 104

思路

树形数组


确定递归函数参数与返回值


返回偷和不偷两种状态下获得的金钱。下标0表示不偷当前节点获得的最大金额,下标1表示偷当前节点获得的最大金额

确定终止条件


遇到空节点,肯定返回 { 0 , 0 }

确定遍历顺序


必须后序遍历,因为要通过递归函数返回值后考虑

确定单层逻辑


如果偷当前节点


左右孩子不能偷,即左右孩子各取下标0的值相加

v a l 1 = c u r . v a l + l e f t [ 0 ] + r i g h t [ 0 ]

如果不偷当前节点


左右孩子可以考虑偷,但到底偷不偷还是要判断

v a l 2 = m a x ( l e f t [ 0 ] , l e f t [ 1 ] ) + m a x ( r i g h t [ 0 ] , r i g h t [ 1 ] )

测试用例



代码展示

class Solution
{
public:
    int rob(TreeNode *root)
    {
        vector result = robTree(root);
        return max(result[0], result[1]);
    }
    vector robTree(TreeNode *cur)
    {
        if (!cur)
        {
            return {0, 0};
        }
        vector curleft = robTree(cur->left);
        vector curright = robTree(cur->right);
        int val1 = cur->val + curleft[0] + curright[0];
        int val2 = max(curleft[0], curleft[1]) + max(curright[0], curright[1]);
        return {val2, val1};
    }
};
目录
相关文章
|
12天前
|
弹性计算 关系型数据库 微服务
基于 Docker 与 Kubernetes(K3s)的微服务:阿里云生产环境扩容实践
在微服务架构中,如何实现“稳定扩容”与“成本可控”是企业面临的核心挑战。本文结合 Python FastAPI 微服务实战,详解如何基于阿里云基础设施,利用 Docker 封装服务、K3s 实现容器编排,构建生产级微服务架构。内容涵盖容器构建、集群部署、自动扩缩容、可观测性等关键环节,适配阿里云资源特性与服务生态,助力企业打造低成本、高可靠、易扩展的微服务解决方案。
1257 5
|
1天前
|
存储 关系型数据库 分布式数据库
PostgreSQL 18 发布,快来 PolarDB 尝鲜!
PostgreSQL 18 发布,PolarDB for PostgreSQL 全面兼容。新版本支持异步I/O、UUIDv7、虚拟生成列、逻辑复制增强及OAuth认证,显著提升性能与安全。PolarDB-PG 18 支持存算分离架构,融合海量弹性存储与极致计算性能,搭配丰富插件生态,为企业提供高效、稳定、灵活的云数据库解决方案,助力企业数字化转型如虎添翼!
|
11天前
|
机器学习/深度学习 人工智能 前端开发
通义DeepResearch全面开源!同步分享可落地的高阶Agent构建方法论
通义研究团队开源发布通义 DeepResearch —— 首个在性能上可与 OpenAI DeepResearch 相媲美、并在多项权威基准测试中取得领先表现的全开源 Web Agent。
1279 87
|
12天前
|
云栖大会
阿里云云栖大会2025年9月24日开启,免费申请大会门票,速度领取~
2025云栖大会将于9月24-26日举行,官网免费预约畅享票,审核后短信通知,持证件入场
1823 13