04141: 砝码称重

recursion, http://cs101.openjudge.cn/practice/04141

设有1g、2g、3g、5g、10g、20g的砝码各若干枚（其总重<=1000），要求：计算用这些砝码能称出的不同重量的个数，但不包括一个砝码也不用的情况。

输入

一行，包括六个正整数a1,a2,a3,a4,a5,a6，表示1g砝码有a1个，2g砝码有a2个，……，20g砝码有a6个。相邻两个整数之间用单个空格隔开。

输出

以“Total=N”的形式输出，其中N为可以称出的不同重量的个数。

样例输入

1 1 0 0 0 0

样例输出

Total=3

提示: 样例给出的砝码可以称出1g，2g，3g三种不同的重量。

来源: NOIP1996复赛提高组第四题

python

# 蒋子轩23工学院
'''
深度优先搜索算法，用于计算一组给定权重的砝码的不同重量组合的数量。

代码中的变量weights是权重列表，表示不同砝码的重量。变量max_w是一个列表，
用于表示每个砝码的最大使用数量。

函数dfs是一个递归函数，用于遍历所有可能的砝码组合。index参数表示当前考虑的砝码索引，
cur_w参数表示当前已经组合的重量。当index等于6时，表示已经尝试了所有的砝码，递归结束。
如果cur_w不等于0，则将其添加到集合w中。递归过程中，
使用一个循环遍历所有可能的使用该砝码个数，并递归调用dfs函数计算下一个砝码的组合。

在主程序部分，将输入的最大使用数量存储在max_w列表中。通过调用dfs(0,0)开始计算所有可能的
砝码重量组合。最后，输出集合w的长度，即不同重量组合的数量。
'''

weights = [1, 2, 3, 5, 10, 20]


def dfs(index, cur_w):
	# 已尝试所有可能砝码，递归结束
    if index == 6:
        if cur_w != 0:
            w.add(cur_w)
        return
    #遍历所有可能的使用该砝码个数
    for i in range(max_w[index]+1):
        dfs(index+1, cur_w+i*weights[index])


max_w = list(map(int, input().split()))
#使用set自动去重
w = set()
dfs(0, 0)
print(f'Total={len(w)}')

04141: 砝码称重 ​

04141: 砝码称重