V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX  ›  yao177  ›  全部回复第 1 页 / 共 8 页
回复总数  147
1  2  3  4  5  6  7  8  
为了解决这个问题,我们可以采用回溯的方法来找到所有符合条件的组合。具体步骤如下:

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 的二开,完美模拟各种快捷键
363 天前
回复了 zzerd 创建的主题 推广 自家赣南脐橙抽奖,华农家同县发出
下了一单,期待
2023-11-18 22:52:32 +08:00
回复了 lijianmin321 创建的主题 分享创造 V 站老哥太热情了, Airy 永久会员加送 9000,凑到 1 万
支持一下!
2023-07-13 19:23:17 +08:00
回复了 chrischris 创建的主题 Apple 求助但有点不好意思: mbp 2019 16 寸如何流畅玩金铲铲之战
我是装了日版 lol 玩云顶
2023-07-11 16:32:44 +08:00
回复了 AaronLee 创建的主题 分享发现 vaultwarden 可以支持 Android 客户端同步了。
马上更新一下试试看,这功能也太好了
2023-04-07 16:41:25 +08:00
回复了 Andor_Chen 创建的主题 推广 送几本“通透”的《流畅的 Python (第 2 版)》
组成分母来了,支持楼主
@jaylee4869 看了下估计是 websocket 实现的,可以抓一下试试
南京的话,省口腔和市口腔都很好就是贵,想省钱就回老家三甲做也行,正规第一位
@ipcjs 感觉 macOS 自带的 screen sharing 更好用
2022-12-13 11:09:50 +08:00
回复了 chihu 创建的主题 问与答 我发现老罗的遗产:锤子便签 没有非常合适的平替
我之前用的 flomo ,现在用 Google keep ,就是不支持富文本
2022-12-06 17:04:41 +08:00
回复了 wuchangming89 创建的主题 OpenAI 体验了下 chatGPT,越玩心越凉
@kemistep 我也有这想法试试看
2022-12-05 15:20:35 +08:00
回复了 ghui 创建的主题 OpenAI 周末把 ChatGPT 接入到了公众号
这是订阅号的问题,只能发一回一。
可不可以搞个消息队列,在超时前发一个默认消息,再让用户发个 continue 来继续对话?
2022-12-02 18:37:41 +08:00
回复了 zyxk 创建的主题 问与答 想问一下大家为什么讨厌 electron 应用呢? 那其他 Web 应用呢 ?
pwa 明显更好用
2022-11-30 14:28:02 +08:00
回复了 GaryLz 创建的主题 分享发现 转帖 未来趋势-无密码体验 谈谈感想
公司里就是 yubikey+okta ,但是这种 zero-trust 判断你异常后解锁就很麻烦了,又是申请又是找管理
2022-11-28 17:13:21 +08:00
回复了 Annihilating 创建的主题 问与答 工作选择:字节飞书还是 Unity 中国云服务
@Annihilating 这个我也不太了解,可以在“酷工作-职场话题”里发帖问问,问与答没啥人看
1  2  3  4  5  6  7  8  
关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   5532 人在线   最高记录 6679   ·     Select Language
创意工作者们的社区
World is powered by solitude
VERSION: 3.9.8.5 · 35ms · UTC 07:16 · PVG 15:16 · LAX 23:16 · JFK 02:16
Developed with CodeLauncher
♥ Do have faith in what you're doing.