yao177

yao177

V2EX 第 400132 号会员,加入于 2019-04-10 08:08:25 +08:00
1 G 7 S 25 B
根据 yao177 的设置,主题列表只有在你登录之后才可查看
二手交易 相关的信息,包括已关闭的交易,不会被隐藏
yao177 最近回复了
为了解决这个问题,我们可以采用回溯的方法来找到所有符合条件的组合。具体步骤如下:

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` 中。我们还使用了一些优化措施,比如跳过重复元素,以减少不必要的计算。

这个算法的时间复杂度较高,对于大数据集可能不够高效,因为它需要检查所有可能的组合。不过,对于小到中等规模的数据集,这个方法应该是可行的。
强烈推荐 kinto ( https://github.com/rbreaves/kinto),基于 autohotkey 的二开,完美模拟各种快捷键
196 天前
回复了 zzerd 创建的主题 推广 自家赣南脐橙抽奖,华农家同县发出
下了一单,期待
支持一下!
我是装了日版 lol 玩云顶
马上更新一下试试看,这功能也太好了
2023-04-07 16:41:25 +08:00
回复了 Andor_Chen 创建的主题 推广 送几本“通透”的《流畅的 Python (第 2 版)》
组成分母来了,支持楼主
2023-03-20 14:39:16 +08:00
回复了 billzhuang 创建的主题 分享发现 一站式 ChatBot 工具由 Quora 出品的 Poe,支持 ChatGPT、Sage 等
@jaylee4869 看了下估计是 websocket 实现的,可以抓一下试试
关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1002 人在线   最高记录 6679   ·     Select Language
创意工作者们的社区
World is powered by solitude
VERSION: 3.9.8.5 · 15ms · UTC 19:44 · PVG 03:44 · LAX 12:44 · JFK 15:44
Developed with CodeLauncher
♥ Do have faith in what you're doing.