没有合适的资源?快使用搜索试试~ 我知道了~
算法设计与分析实验4 :利用动态规划的方法解决子集等和分割判断问题
需积分: 5 0 下载量 201 浏览量
2024-01-17
21:44:45
上传
评论
收藏 58KB DOC 举报
温馨提示
试读
5页
实验4 利用动态规划的方法解决子集等和分割判断问题 一、实验目的 1. 了解动态规划的主要思想。 2. 掌握背包问题解决方法用以解决该问题。 3. 分析核心代码的时间复杂度和空间复杂度。 二、实验内容和要求 题目:给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。 注意: 每个数组中的元素不会超过 100 数组的大小不会超过 200 示例 1: 输入: [1, 5, 11, 5] 输出: true 解释: 数组可以分割成 [1, 5, 5] 和 [11]. 示例 2: 输入: [1, 2, 3, 5] 输出: false 解释: 数组不能分割成两个元素和相等的子集. 【请说明动态规划算法的核心思想】 动态规划方法是一种对具有交叠子问题的问题进行求解的技术。一般来说,这样的子问题出现在求解给定问题的递推关系中,这个递推关系中包含了相同类型的更小子问题的解。动态规划法建议,与其对交叠的子问题一次又一次地求解,还不如对每个较小的子问题只解一次并把结果记录在表中,这样就可以从表中得出原始问题的解。
资源推荐
资源详情
资源评论
1
实验 4 利用动态规划的方法解决子集等和分割判断问题
一、实验目的
1. 了解动态规划的主要思想。
2. 掌握背包问题解决方法用以解决该问题。
3. 分析核心代码的时间复杂度和空间复杂度。
二、实验内容和要求
题目:给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集,使得两
个子集的元素和相等。
注意:
每个数组中的元素不会超过 100
数组的大小不会超过 200
示例 1:
输入: [1, 5, 11, 5]
输出: true
解释: 数组可以分割成 [1, 5, 5] 和 [11].
示例 2:
输入: [1, 2, 3, 5]
输出: false
解释: 数组不能分割成两个元素和相等的子集.
【请说明动态规划算法的核心思想】
动态规划方法是一种对具有交叠子问题的问题进行求解的技术。一般来说,这样的
子问题出现在求解给定问题的递推关系中,这个递推关系中包含了相同类型的更小子问题
的解。动态规划法建议,与其对交叠的子问题一次又一次地求解,还不如对每个较小的子
问题只解一次并把结果记录在表中,这样就可以从表中得出原始问题的解。
【请说明背包问题与题目之间的关联性在哪】
找两个相等的子集问题,可以转化为求:是否存在一些正整数可以组成数组和 Sum 的
一半。这样子可以看成是一个背包问题:一共有 n 个物品(数),每个物品(数)只能被选
资源评论
Blossomi
- 粉丝: 1w+
- 资源: 89
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功