ACDaily 5
本文最后更新于:3 个月前
从集合角度分析DP问题
算法特点
一般问法:最值(价值等属性)、达到某一目标的方向总数
背包问题的本质为组合问题,即在一定条件下从一部分物品中挑选物品;同时也类似于图论的最短路,可以说,DP是一种特殊的图论
暴力做法:方案数量为指数级
化零为整:挖掘不同方案间的共同关系,把有相同关系的元素放在一起
化整为零:把一个集合划分为多个子集,进行分析
解决问题的过程中一定抓住从实际含义出发
具体的分析在下述例题中会有解释
题解的优化可以参考ACDaily 4
01背包
有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。
第 i 件物品的体积是 vi,价值是 wi。
求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。
输出最大价值。
本题题解具体优化可以参考ACDaily 4,此处借此例讲解动态规划基本的算法架构
算法架构:动态规划集合化
状态表示(一般为二维,不可能超时)
f[i][j]
- 集合的思想,
f[i][j]
表示的并非是j体积背包下对前i个物品进行选择下的价值最大值,而是j体积下对前i个物品进行选择下的所有方案的最大价值(每个物品可选可不选) - 属性:min、max、count,即数组中的元素表示最值或方案数
- 集合的思想,
状态计算(化零为整)
- 集合的划分,划分依据:最后一个不同点。即在限制条件下(确定问题域),按选或不选第i个物品(i个物品中的最后物品)对方案进行划分为A(选i)和B(不选i)集合
- 要求:不重不漏,每个子集中的元素具有相同共性(都选或没选第i个物品),各子集又能组合成全集
- 对不选i的集合中(B)所有方案的最大价值进行计算,得到max1
- 按物品选择是否发生变化,对上述划分包含选择第i个物品的方案(即A方案集合)进行分区,物品i所在区域为不变区,前i-1个物品组成的区域为变化区
- 寻找变化区中总价值最大的物品选择方案,加上第i个物品的价值,得到最大价值max2
- 求
max(max1, max2)
,得到整体最大价值
关键在于选择划分方式,例如以下的摘花生与最大子序列长度
- 集合的划分,划分依据:最后一个不同点。即在限制条件下(确定问题域),按选或不选第i个物品(i个物品中的最后物品)对方案进行划分为A(选i)和B(不选i)集合
1. 摘花生
Hello Kitty想摘点花生送给她喜欢的米老鼠。
她来到一片有网格状道路的矩形花生地(如下图),从西北角进去,东南角出来。
地里每个道路的交叉点上都有种着一株花生苗,上面有若干颗花生,经过一株花生苗就能摘走该它上面所有的花生。
Hello Kitty只能向东或向南走,不能向西或向北走。
问Hello Kitty最多能够摘到多少颗花生。
输入格式
第一行是一个整数T,代表一共有多少组数据。
接下来是T组数据。
每组数据的第一行是两个整数,分别代表花生苗的行数R和列数 C。
每组数据的接下来R行数据,从北向南依次描述每行花生苗的情况。每行数据有C个整数,按从西向东的顺序描述了该行每株花生苗上的花生数目M。
输出格式
对每组输入数据,输出一行,内容为Hello Kitty能摘到得最多的花生颗数。
数据范围
1≤T≤100,
1≤R,C≤100,
0≤M≤1000
输入样例:
2
2 2
1 1
3 4
2 3
2 3 4
1 6 5
输出样例:
8
16
题解:
1 |
|
2. 最长上升子序列
给定一个长度为 N 的数列,求数值严格单调递增的子序列的长度最长是多少。
输入格式
第一行包含整数 N。
第二行包含 N 个整数,表示完整序列。
输出格式
输出一个整数,表示最大长度。
数据范围
1≤N≤1000,
−109≤数列中的数≤109
输入样例:
7
3 1 2 1 8 5 6
输出样例:
4
题解:
1 |
|
3. 地宫寻宝
X 国王有一个地宫宝库,是 n×m 个格子的矩阵,每个格子放一件宝贝,每个宝贝贴着价值标签。
地宫的入口在左上角,出口在右下角。
小明被带到地宫的入口,国王要求他只能向右或向下行走。
走过某个格子时,如果那个格子中的宝贝价值比小明手中任意宝贝价值都大,小明就可以拿起它(当然,也可以不拿)。
当小明走到出口时,如果他手中的宝贝恰好是 k 件,则这些宝贝就可以送给小明。
请你帮小明算一算,在给定的局面下,他有多少种不同的行动方案能获得这 k 件宝贝。
输入格式
第一行 3 个整数,n,m,k,含义见题目描述。
接下来 n 行,每行有 m 个整数 Ci 用来描述宝库矩阵每个格子的宝贝价值。
输出格式
输出一个整数,表示正好取 k 个宝贝的行动方案数。
该数字可能很大,输出它对 1000000007 取模的结果。
数据范围
1≤n,m≤50,
1≤k≤12,
0≤Ci≤12
输入样例1:
2 2 2
1 2
2 1
输出样例1:
2
输入样例2:
2 3 2
1 2 3
2 1 5
输出样例2:
14
题解:
1 |
|
本文作者: waitingFor
本文链接: http://example.com/2022/03/05/ACDaily/ACDaily-5/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!