动态规划子集合类题

给定一个目标值M和一个组set S ＝ {S0，S1，S2，.... Sn-1}，其中Si包含一个整数值"number"和一个boolean value ："marked" 例如：Si.number =5， Si.marked =true or false
题目为:
找出是否存在一个子集合s’ 使得子集合的number 之和为目标值 且 Si.marked 为true 的element 小于50

请问这题要如何使用动态规划的方法解

一般的，subset sum类问题是NP完全问题，不限定集合内元素的取值范围的话，需要指数时间。
比如楼主的这个题，如果 S_i.marked 全部都是 false，就退化到一般的 subset sum，没法保证时间复杂度。

做一个更强的假设，如果集合内的元素之和在一个 reasonable 的范围之内，那就正常的 DP 即可。多了一个 S_i.marked 的条件（我猜意思是 marked 为 true 的元素个数之和小于50吧？），无非就是多加一个状态代表子集内 S_i.marked 的元素个数，变成一个二元组 <子集元素和, 子集内 marked 元素个数>。

maristie 发表于 2021-5-3 11:31
一般的，subset sum类问题是NP完全问题，不限定集合内元素的取值范围的话，需要指数时间。
比如楼主的这个 ...

原本子集和解法是dp[i][j] 表示可以利用s0...sj 组成 j 的目标值, 如果我再加一个状态变成dp[i][j][count] count 表示marked 为true之个数，想请问那么Runtime还是 Ｏ（nM）吗？

对于不带 marked 限制的原来的子集和问题，用 n 表示元素个数，用 M 表示子集和的范围大小 (比如任意子集和都落在 [a, b] 的整数区间内，则 M = b - a + 1)，则 runtime 是 楼主说的 O(nM).

对于这个问题，从左到右扫描这个 set S，对每个元素，最坏情况下我们都要 check 并 update dp[j][count] 这个二维数组里的每个元素，所以 runtime 是 O(nMc)，c = 50（当然也可以是非固定的参数，只要不是太大）。