Python基于回溯法子集树模板解决取物搭配问题实例
作者:罗兵 发布时间:2023-11-20 04:46:53
标签:Python,回溯法
本文实例讲述了Python基于回溯法子集树模板解决取物搭配问题。分享给大家供大家参考,具体如下:
问题
有5件不同的上衣,3条不同的裤子,4顶不同的帽子,从中取出一顶帽子、一件上衣和一条裤子作为一种搭配,问有多少种不同的搭配?
分析
换个角度看,现有头、身、腿三个元素,每个元素都有各自的几种状态。
头元素有['帽1', '帽2', '帽3', '帽4']共4种状态,身元素有['衣1', '衣2', '衣3', '衣4', '衣5']共5种状态,腿元素有['裤1', '裤2', '裤3']共3种状态
从头开始,自上而下,遍历每个元素的所有状态。
解的长度是固定的。
这里特别注意:每个元素的状态数目不同!!!
套用子集树模板即可
代码
```python
'''取物排列问题'''
n = 3 # 3个元素
头、身、腿3个元素各自的状态空间
a = [['帽1', '帽2', '帽3', '帽4'],
['衣1', '衣2', '衣3', '衣4', '衣5'],
['裤1', '裤2', '裤3']]
x = [0]*n # 一个解,长度固定,3元数组
X = [] # 一组解
冲突检测
def conflict(k):
return False # 无冲突
套用子集树模板
def match(k): # 到达第k个元素
global n, a, x, X
if k >= n: # 超出最尾的元素
print(x)
#X.append(x[:]) # 保存(一个解)
else:
for i in a[k]: # 直接a[k],若间接则range(len(a[k]))。 遍历第k个元素的对应的所有选择状态,不同的元素状态数目不同
x[k] = i
if not conflict(k): # 剪枝
match(k+1)
测试
match(0) # 从头(第0个元素)开始
效果图
希望本文所述对大家Python程序设计有所帮助。
来源:http://www.cnblogs.com/hhh5460/p/6920671.html
0
投稿
猜你喜欢
- photoshop快捷键大全: 工具箱(多种工具共用一个快捷键的可同时按【Shift】加此快捷键选取)相关文章:网页设计软件FrontPag
- 我和朋友对此的看法有分歧,我明明记得有不需要返回的时候的?你的看法是对的,例如在表中删除记录。我们来看看下面的例子——在Employee表中
- 建立一个数据库表维护规范在一个定期基础而非等到问题出现才实施数据库表的检查是一个好主意。应该考虑到建立一个预防性维护的时间表,以协助自动问题
- 在url网址中,我们经常使用server.urlencode来对网址进行编码,特别是遇到网址中有中文字符的时候,如<a href=&q
- 在我们制作主页的过程中,用到表格的地方非常多,灵活运用表格技巧可以为我们的网页增色不少,这里我就详细介
- 代码如下:'其中注释中有 ###的需要用户设置 '其中注释中有 参数传递 ** 的 说明要通过参数 传递。'定义变量
- 本文实例讲述了python计算一个序列的平均值的方法。分享给大家供大家参考。具体如下:def average(seq, total=0.0)
- //获取字符数组String.prototype.ToCharArray=function() { &n
- 前端技术层(图片有点偏激,仅供参考)Javascript和DOM关系很暧昧,弄不明白!CSS和HTML
- 一个Javascript 的类库,用于table内容排序。使用很方便,不用每次都去调用数据库了。特别适合多表查询的排序。加上<tbod
- 由于Internet的历史原因,apin负责整个网络IP的整体规划以及北美区
- 前言超时,指一个协程A开启另一个协程B,A会阻塞等待B一段指定的时间,例如:5秒,A通知B结束(也有可能不通知,让B继续运行)。也就是说,A
- 网站,(100-1)%的内容是导航1、Jesse James Garrett 在《用户体验要素》一书中提到了多重导航系统:全局导航、局部导航
- 本文实例讲述了Codeigniter发送邮件的方法。分享给大家供大家参考。具体分析如下:Codeigniter的邮件发送支持一下特性:Mul
- Google中秋的logo出来了,酷似一美男站在月亮上,结果被网友弄出一撒尿版来。中国网民好智慧啊~原logo: 撒尿版logo:
- 将有安全问题的SQL过程删除.比较全面.一切为了安全!删除了调用shell,注册表,COM组件的破坏权限MS SQL SERVER2000使
- 迭代器模式迭代器模式(Iterator Pattern)是一种常用的设计模式,用于遍历集合中的元素,不暴露集合的内部结构。迭代器模式将集合和
- //重新封装document对象 var Console={ Write:function(msg){alert(msg);} }; //P
- 众所周知,pip 可以安装、更新、卸载 Python 的第三方库,非常方便。你们中的许多人可能已经使用 pip 
- 现在大家都在讨论Web2.0 ,大家都在搞用户行为前端设计,现在注册一个ID一般只需要几秒钟,站长期望其产生高价值的UGC,形成一个只需要审