Python基于回溯法子集树模板解决取物搭配问题实例
作者:罗兵 时间:2023-11-20 04:46:53
本文实例讲述了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
标签:Python,回溯法
0
投稿
猜你喜欢
python 多进程和多线程使用详解
2021-08-12 19:50:43
如何在SQL Server数据库中加密数据
2008-12-18 14:27:00
Golang连接Redis数据库的方法
2024-01-16 09:35:22
Python两台电脑实现TCP通信的方法示例
2023-09-07 04:17:34
CSS实例教程:复合型CSS条状图表(上)
2010-01-23 12:43:00
python 实现按对象传值
2023-05-26 14:20:18
使用javascript+xml技术实现分页浏览
2008-05-29 13:49:00
基于JS实现01支付后的10秒倒计时
2024-04-10 11:02:30
MySQL 备份还原数据库批处理
2024-01-16 21:03:52
php版银联支付接口开发简明教程
2023-11-24 00:27:41
JS实现jQuery的append功能
2024-04-22 22:23:00
Python中extend和append的区别讲解
2021-03-28 04:20:37
使用SQL语句将相同名的多行字段内容拼接(方法详解)
2024-01-15 00:11:13
python利用tkinter实现图片格式转换的示例
2023-10-10 05:10:22
960 Grid System 基本原理及使用方法
2009-02-28 13:35:00
JavaScript模块规范之AMD规范和CMD规范
2024-04-30 08:52:46
python实现ip地址查询经纬度定位详解
2021-09-13 08:01:52
vantUI 获得piker选中值的自定义ID操作
2024-04-10 13:48:42
django template实现定义临时变量,自定义赋值、自增实例
2021-05-24 09:16:46
Go语言包管理工具Godep的用法
2024-02-20 04:09:44