例如: 输入: candidates = [10, 20, 20, 30, 40], [min, max] = [30, 50] 输出: [[10, 20], [10, 30], [10, 40], [10, 20, 20], [20, 20], [20, 30], [30], [40]]
例如: 输入: candidates = [10, 20, 20, 30], target = 45, target1 = 10 输出: [[20, 30], [10, 20, 20]]
以上都是我这边现实业务需要计算的场景, 我根据 leetcode 上的组合总和 II改了改算是勉强将第一个算法实现了
第二个算法实在是不会搞了
1
kamilic 231 天前
不是很懂算法,但以前有了解过一些 leetcode 解法。
我觉得先考虑先粗暴做出来,再进行性能优化? 先从 candidates 中找出字和 > target 的输出 A ,再从 A 中找 < target 的输出 B , 再从 B 中找 <= target - target1 的组合 C 。 优化方向的话,在查找组合和的过程中,应该有很多运算结果可以复用的。 |
2
yao177 231 天前
为了解决这个问题,我们可以采用回溯的方法来找到所有符合条件的组合。具体步骤如下:
1. **排序**:首先对数组 `candidates` 进行排序,这有助于优化搜索过程并减少重复。 2. **回溯**:通过递归函数遍历所有可能的组合,并在每个步骤中进行条件检查。 3. **条件检查**: - 确保当前组合的和大于 `target`。 - 对于当前组合中的每个元素,移除该元素后的和应小于 `target`。 - 对于当前组合中的每个元素,移除该元素后的和应小于或等于 `target - target1`。 下面是一个 Python 实现的例子: ```python def find_combinations(candidates, target, target1): candidates.sort() # 排序以优化搜索 results = [] def backtrack(comb, start, current_sum): # 检查当前组合是否满足条件 if current_sum > target: # 检查移除任意一个元素后是否满足所有条件 all_valid = True for i in range(len(comb)): new_sum = current_sum - comb[i] if new_sum < target and new_sum <= target - target1: continue else: all_valid = False break if all_valid: results.append(comb.copy()) return # 继续添加元素到组合中 for i in range(start, len(candidates)): # 为了避免重复组合,跳过相同的元素 if i > start and candidates[i] == candidates[i - 1]: continue comb.append(candidates[i]) backtrack(comb, i + 1, current_sum + candidates[i]) comb.pop() # 回溯 backtrack([], 0, 0) return results # 示例输入 candidates = [10, 20, 20, 30] target = 45 target1 = 10 # 函数调用 output = find_combinations(candidates, target, target1) print(output) ``` 这个代码首先定义了一个回溯函数 `backtrack`,该函数尝试在 `candidates` 中找到所有符合条件的组合。我们使用 `comb` 来存储当前的组合,使用 `current_sum` 来跟踪当前组合的总和。如果当前组合满足所有条件,我们将其添加到结果列表 `results` 中。我们还使用了一些优化措施,比如跳过重复元素,以减少不必要的计算。 这个算法的时间复杂度较高,对于大数据集可能不够高效,因为它需要检查所有可能的组合。不过,对于小到中等规模的数据集,这个方法应该是可行的。 |
3
dhb233 231 天前
这是在算优惠券吗[doge]
|
4
MoYi123 231 天前
candidates = [10, 20, 20, 30, 40]
target = 45 target1 = 10 from functools import cache @cache def dp(idx, count, min_element, max_element): if idx == len(candidates): ________if count > target and count - min_element < target and count - max_element <= target - target1: ____________print(count, min_element, max_element) ____________return 1 ________return 0 ____if not count - min_element < target: ________return 0 ____ele = candidates[idx] ____pick = dp(idx + 1, count + ele, min(ele, min_element), max(ele, max_element)) ____not_pick = dp(idx + 1, count, min_element, max_element) ____return pick + not_pick print(dp(0, 0, 4e18, 0)) O(n^3 * target) 只有方案数, 具体方案是什么你自己改一下. |
5
main1234 231 天前
func reverse(arr []int, target1, target2 int) [][]int {
res := make([][]int, 0) // 先排序 sort.Ints(arr) // 逆序排序 for i := 0; i < len(arr)/2; i++ { arr[i], arr[len(arr)-i-1] = arr[len(arr)-i-1], arr[i] } sum := 0 track := make([]int, 0) var fn func(start int) fn = func(start int) { if start == len(arr) { if sum < target1 && sum-track[len(track)-1] < target1 && sum-track[len(track)-1] < target1-target2 { tmp := make([]int, len(track)) copy(tmp, track) res = append(res, tmp) return } } for i := start; i < len(arr); i++ { sum += arr[i] track = append(track, arr[i]) fn(i + 1) track = track[:len(track)-1] sum -= arr[i] } } fn(0) return res } |
6
main1234 231 天前
我的算法应该能继续剪枝
|
7
bthulu OP @main1234 你这个算法有问题啊,
if sum < target1 && sum-track[len(track)-1] < target1 && sum-track[len(track)-1] < target1-target2 是不是应该改成 if sum > target1 ... |
10
lecia 231 天前 via iPhone
第一问,01 背包记忆化,最后回溯结果输出。或者递归搜索剪枝也行。
第二问,取第一问结果大于 target 的方案,对每个方案 check ,此方案的每个数字> 方案和-target ,且至少存在一个数字>=方案和-target+target1 第二问递归剪枝感觉能好很多,剪枝条件就是问题中的两个不等式 |
11
main1234 231 天前
@bthulu
func reverse(arr []int, target1, target2 int) [][]int { res := make([][]int, 0) // 先排序 sort.Ints(arr) // 逆序排序 for i := 0; i < len(arr)/2; i++ { arr[i], arr[len(arr)-i-1] = arr[len(arr)-i-1], arr[i] } sum := 0 track := make([]int, 0) var fn func(start int) fn = func(start int) { if sum > target1 && sum-track[len(track)-1] < target1 && sum-track[len(track)-1] <= target1-target2 { tmp := make([]int, len(track)) copy(tmp, track) res = append(res, tmp) return } for i := start; i < len(arr); i++ { if sum-arr[i] >= target1 { continue } if sum-arr[i] >= target1-target2 { continue } sum += arr[i] track = append(track, arr[i]) fn(i + 1) track = track[:len(track)-1] sum -= arr[i] } } fn(0) return res } |
12
Sawyerhou 231 天前 via Android
不知道理解的对不对,目前赞成 10 楼的思路
算法 1 备选方案中,剔除最大元素小于 sum-target+distance 的 |
13
todd7zhang 231 天前
反正都输出所有集合了,直接暴力回溯,只要回溯的时候注意去掉重复的就行
```python def solution2(arr: list[int], lo:int, hi:int) -> list[list[int]]: def valid(temp): return all([ sum(temp) > hi, all((sum(temp[:_i]) + sum(temp[_i+1:])) < hi for _i in range(len(temp))), any((sum(temp[:_i]) + sum(temp[_i+1:])) <= hi - lo for _i in range(len(temp))), ]) def backtrack(i:int): if i >= len(arr): return for j in range(i, len(arr)): if j == i or arr[j] != arr[j-1]: temp.append(arr[j]) if valid(temp): res.append(temp[:]) backtrack(j+1) temp.pop() temp = [] res = [] arr.sort() backtrack(0) return res # solution2([10, 20, 20, 30], 10, 45) -> [[10, 20, 20], [20, 30]] ``` |
14
todd7zhang 231 天前
代码乱了,哈哈。直接看 code 链接呢 https://paste.ofcode.org/iHEThFKxvkXHbhmMjAy4TB
|
15
forty 231 天前
不考虑性能,用排列组合,生成所有的组合,符合范围的组合就存入结果。
把判别函数作为参数,这样你需要什么样条件的组合,只需要给不同的判别函数进行调用就行,没什么难的。 |
16
cpstar 231 天前
应该是深度优先和递归,一个数字只能用一次,然后先取一个数,判断<t1 ,继续取数,直到 t1<sum<t ,作为成功,然后如果 sum>t 则失败弹栈。
|
17
meilicat 230 天前
数据范围呢?
|