我想知道是否存在解决此问题的算法。这与背包0-1问题或幂集问题有些相似,但又不同。
给定一组有限的已排序实数,我们需要生成所有可能的子集,其和小于等于k。这里k是实数,已排序的实数都为正数。例如,一个数组={1.48, 2.21, 3.07, 4.35, 4.46},k=5.94。输出结果为:{4.46},{4.46, 1.48},{4.35},{4.35, 1.48},{3.07},{3.07, 2.21},{2.21},{2.21, 1.48}和{1.48}。
解决这个问题的一种方法是从最高的数字{4.46}开始遍历,看你可以在篮子里包含多少个数字,然后继续下一个较低的数字 {4.35}等等。有没有一种有效的方法来做到这一点?请告诉我。
给定一组有限的已排序实数,我们需要生成所有可能的子集,其和小于等于k。这里k是实数,已排序的实数都为正数。例如,一个数组={1.48, 2.21, 3.07, 4.35, 4.46},k=5.94。输出结果为:{4.46},{4.46, 1.48},{4.35},{4.35, 1.48},{3.07},{3.07, 2.21},{2.21},{2.21, 1.48}和{1.48}。
解决这个问题的一种方法是从最高的数字{4.46}开始遍历,看你可以在篮子里包含多少个数字,然后继续下一个较低的数字 {4.35}等等。有没有一种有效的方法来做到这一点?请告诉我。
pi
或sqrt(2)
是否合法? - amitk
是 子集和问题,这是 NP-难问题。 - amit