完美项链算法题-Python解法

完美项链的算法

题目：

完美项链:
小华有N种不同颜色的珠子，每种珠子有一定的数量，他想用这些珠子做项链。
其中没串项链需要M个珠子，且要求每串项链中不能有颜色相同的珠子
请问小华最多能做多少串项链。

例1:
N=4，结合一定数量珠子为{“1”:6,“2”:9,“3”:7,“4”:4},此时珠子总数量为26
M=3
那么输出有
[
(‘2’, ‘3’, ‘1’)
(‘2’, ‘3’, ‘1’)
(‘2’, ‘3’, ‘1’)
(‘2’, ‘3’, ‘4’)
(‘2’, ‘1’, ‘3’)
(‘2’, ‘4’, ‘1’)
(‘2’, ‘3’, ‘4’)
(‘2’, ‘1’, ‘3’)
]
共8条链子，最后剩余珠子为{‘1’: 0, ‘2’: 1, ‘3’: 0, ‘4’: 1}

解题思路：

目前我想到的解题思路是使用递归：
递归算法的三部曲：

1. 递归函数参数定义和返回值
2. 确定递归终止条件
3. 递归单次的逻辑

根据上述方式，解读题目后：
递归函数的参数定义返回值：参数为组成链子的珠子数目M，全局变量（非递归内）变量count记录链子数，全局变量字典dict_temp记录当前剩余珠子的状态
确定递归终止条件：单个珠子数量大于0的种数<组成链子珠子数目M
单次递归的逻辑：从珠子数量最大的三个中选取珠子，然后项链数+1，被选中的珠子的数量-1, 继续递归

最后直接上代码：

from copy import deepcopy
def func(dict1,N,M):"""解题思路：使用递归函数递归函数的参数定义返回值：参数为组成链子的珠子数目M，全局变量（非递归内）变量count记录链子数，全局变量字典dict_temp记录当前剩余珠子的状态确定递归终止条件：单个珠子数量大于0的种数<组成链子珠子数目M单次递归的逻辑：从珠子数量最大的三个中选取珠子，然后项链数+1，被选中的珠子的数量-1, 继续递归"""dict_temp = deepcopy(dict1)count=0return_ls=[]def digui(M):nonlocal count #引用nonlocal变量# 确定递归终止条件：单个珠子数量大于0的种数<组成链子珠子数目Mcount_lager_than_zero=0for k,v in dict_temp.items():if v>0:count_lager_than_zero +=1if count_lager_than_zero<M:return# 从珠子数量最大的三个中选取珠子，然后项链数+1，被选中的珠子的数量-1, 继续递归 L_temp=[] #用于记录前M个数量最大的珠子while True:if len(L_temp)==M:for i in L_temp:dict_temp[i]= dict_temp[i]-1count += 1return_ls.append(tuple(L_temp))breakfor i in range(M):max_value_temp=0key_temp=""for k,v in dict_temp.items():if v>max_value_temp and (k not in L_temp):max_value_temp=vkey_temp=kL_temp.append(key_temp)   digui(M)digui(M)return count,dict_temp,return_lsN=4
M=3
dict1={"1":6,"2":9,"3":7,"4":4}
count,dict1,ls=func(dict1,N,M)
print(count)
print(dict1)
for k in ls:print(k)

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！