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
投稿猜你喜欢
有一个多选的需求，在网上找到了这个插件：multiselect https://github.com/ehynds/jquery-ui-mu- mysql行转列、列转行 语句不难，不做多余解释了，看语句时，从内往外一句一句剖析行转列 &nb
- 什么是字典字典是Python中最强大的数据类型之一，也是Python语言中唯一的映射类型。映射类型对象里哈希值(键,key)和指向的对象(值
- 本文实例讲述了Python通过公共键对字典列表排序算法。分享给大家供大家参考，具体如下：问题：想根据一个或多个字典中的值来对列表排序解决方案
- 一：区别：1、var声明的变量属于函数作用域，而let和const声明的变量属于块级作用域；（js作用域在上篇文章） 2、var声
- 管理认证系统最简单的方法是通过管理界面。然而，当你需要绝对的控制权的时候，有一些低层 API 需要深入专研，我们将在下面的章节中讨论它们。创
- 示例很简单，注释里也都做了说明，这里就不多废话了。<?php/*从平台获取数据库名*/$dbname = "";/
- 为庆祝jQuery的四周年生日，jQuery官方团队正式发布了jQuery 1.4版本。在这个版本中，jQuery官方团队做了大量的编码、测
- 一.安装python进入python官网,点击依次点击红色选中部分，开始下载。。。下载完成后，打开安装包，如下有两个选项，一个是立即安装，另
- 最终效果前言这是最近在学qt这个东西，然后又学会了调用api，然后就想了用pyqt5做一个GUI界面，后期也可以打包分享给其他人使用，所以就
- 本文以实例形式分析了Python多进程编程技术，有助于进一步Python程序设计技巧。分享给大家供大家参考。具体分析如下：一般来说，由于Py
- 要使用摄像头，需要使用cv2.VideoCapture(0)创建VideoCapture对象，参数0指的是摄像头的编号，如果你电脑上有两个摄
- 我的风格，废话不多说了，直接给大家贴代码了，并在一些难点上给大家附了注释，具体代码如下所示：#!/usr/bin/env python#-*
- 背景在小站点上，直接用git来部署php代码相当方便，你的远程站点以及本地版本库都有一个版本控制，追踪问题或者回滚是很轻松的事情。因为在小公
- 本文实例讲述了Python实现的计算器功能。分享给大家供大家参考，具体如下：源码：# -*- coding:utf-8 -*-#! pyth
- python networkx来生成一个图使用python提供的第三方的库networkx，networkx是专门用来生成图论和网络科学里面
- 使用python完成超级基础的学生管理系统，供大家参考，具体内容如下说明：1、本学生管理系统非常非常简易，只有增，显，查，删，改功能，对于P
- 这个程序将记数器的数字放在ACCESS数据库中,当然你也能用你希望其它的ODBC数据源.这个程序从URL中读取记数信息.如下:< IM
- 一、Go interface 介绍interface 在 Go 中的重要性说明interface 接口在 Go 语言里面的地位非常重要，是一
- 这个间歇性向上滚动js代码很适合做广告展示，友情链接等等。与平常的无缝向上连续滚动不同的是它每滚动一个就会停顿一会儿。<!DOCTYP
