Python基于回溯法子集树模板解决取物搭配问题实例

yipeiwu_com7年前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相关内容感兴趣的读者可查看本站专题:《Python数据结构与算法教程》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》及《Python入门与进阶经典教程》

希望本文所述对大家Python程序设计有所帮助。

相关文章

Python获取指定字符前面的所有字符方法

在用C和python编程时遇到的一个问题是: 用网口发送过来1k数据,数据格式是json,但是发送时不知道需要的大小,因为不同任务大小不一样,所以统一发送1024字节,统一接收1024了...

Python3实现二叉树的最大深度

Python3实现二叉树的最大深度

问题提出: 给定一个二叉树,找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。 说明: 叶子节点是指没有子节点的节点。 解决思路:递归法求解。从根结点向下遍历,...

idea创建springMVC框架和配置小文件的教程图解

idea创建springMVC框架和配置小文件的教程图解

这个框架主要还是思想,之后,,,还是创建项目好了, 1.新建一个项目 新建一个maven,并且选择webapp类型。 2.点击next选项 这里面的两个选项可以随便填,但是Artif...

对python产生随机的二维数组实例详解

最近找遍了python的各个函数发现无法直接生成随机的二维数组,其中包括random()相关的各种方法,都没有得到想要的结果。最后在一篇博客中受到启发,通过列表解析的方法得到随机的二维数...

Python将多份excel表格整理成一份表格

利用Python将多份excel表格整理成一份表格,抛弃过去逐份打开复制粘贴的方式。 直接附上代码: import xlrd import xlwt import os fro...