python 回溯法 子集树模板 系列 —— 5、取物搭配问题-阿里云开发者社区

开发者社区> 吞吞吐吐的> 正文

python 回溯法 子集树模板 系列 —— 5、取物搭配问题

简介:
+关注继续查看

问题

有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个元素)开始

```

效果图

709432-20170530161328930-864745624.jpg

本文转自罗兵博客园博客,原文链接:http://www.cnblogs.com/hhh5460/p/6920671.html,如需转载请自行联系原作者

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
动态规划法(三)子集和问题(Subset sum problem)
  继续讲故事~~   上次讲到我们的主人公丁丁,用神奇的动态规划法解决了杂货店老板的两个找零钱问题,得到了老板的肯定。之后,他就决心去大城市闯荡了,看一看外面更大的世界。
1670 0
java模仿qq好友面板的布局(BoxLayout问题)
        ..............               JLabel ll = new JLabel(dlg.getNameText() + ":" + dlg.getIPText(), ii[index], JLabel.
492 0
一个由mobx observer引发的React Route路由失效问题探究
## 1. 问题描述 最近一直在使用React + React Router(v4.1.1) + Mobx做项目开发,相比繁琐的React + React Rotuer + Redux方案,爽的不要不要的,当然前提你得忍受Object.defineProperty拦截getter/setter带来的各种黑魔法问题。咳咳,这里不是Mobx大战Redux,就此打住。想了解的人可以去看一下女神Pree
4537 0
4852
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载