求和为定值的任意个数的所有组合(子集和问题) - ruby实现

递归解法:
#!/usr/bin/ruby
$result_array=[]
puts 'input data(array)'  
data_array=gets.split(",").map!{|element|element.to_i}.sort!  
puts 'input k(sum)'  
k=gets.to_i

data_array.map!{|element|element if element>0&&element<=k}.compact! #删除数组中不符合条件的数(<=0或>k)

def alg(array,n,k)  
    if (n<=0||k<0) #失败
        return
    end
    if (array[n-1]==k) #done,输出
        print $result_array.join('+') + '+' + array[n-1].to_s + "\n"
        return
    end
    $result_array.push(array[n-1])
    alg(array,n-1,k-array[n-1]) #如果取这个数
    $result_array.pop
    alg(array,n-1,k) #如果不取这个数
end

alg(data_array,data_array.size,k) #run  

尬文:

嘛...这个算是背包问题的魔改版同时也好像是最简单的NPC问题的说。

NP完全问题我是第一次接触,确实挺难的(可能是我比较笨吧w)

非递归解法也许会在以后给出...

如果能帮到有需要的人那真是再好不过了w

点击右边的按钮加载评论,如果无法加载那估计是被墙啦..你看着办w