子集和问题的Python程序
在本文中,我们将学习下面给出的问题陈述的解决方案。
问题陈述-我们在数组中获得了一组非负整数和一个值总和,我们需要确定是否存在该给定集合的子集且总和等于给定总和。
现在让我们在下面的实现中观察解决方案-
#天真的方法
示例
def SubsetSum(set, n, sum) : # Base Cases if (sum == 0) : return True if (n == 0 and sum != 0) : return False # ignore if last element is > sum if (set[n - 1] > sum) : return SubsetSum(set, n - 1, sum); # else,we check the sum # (1) including the last element # (2) excluding the last element return SubsetSum(set, n-1, sum) or SubsetSum(set, n-1, sumset[n-1]) # main set = [2, 14, 6, 22, 4, 8] sum = 10 n = len(set) if (SubsetSum(set, n, sum) == True) : print("Found a subset with given sum") else : print("No subset with given sum")
输出结果
Found a subset with given sum
#动态方法
示例
# maximum number of activities that can be performed by a single person def Activities(s, f ): n = len(f) print ("所选活动为:") # The first activity is always selected i = 0 print (i,end=" ") # For rest of the activities for j in range(n): # if start time is greater than or equal to that of previous activity if s[j] >= f[i]: print (j,end=" ") i = j # main s = [1, 2, 0, 3, 2, 4] f = [2, 5, 4, 6, 8, 8] Activities(s, f)
输出结果
Found a subset with given sum
结论
在本文中,我们学习了如何为子集和问题编写Python程序。