fork download
copy 
  1. def sum(list)
  2. 	a = 0
  3. 	list.each { |i| a += i }
  4. 	return a
  5. end
  6.  
  7. def listup(a, limit_value)
  8. 	ans = []
  9. 	first = a[0]
  10.  
  11. 	# 要素がひとつだったら、限界値を超えていなければ、解として採用
  12. 	if a.size == 1 then
  13. 		if first <= limit_value then
  14. 			ans = [[ first ]]
  15. 		end
  16.  
  17. 	# 要素が複数
  18. 	else
  19. 		# 先頭の値が限界値以下なら、それを除いたリストに対して、
  20. 		# 「限界値－先頭の値」を限界値として、探索
  21. 		b = []
  22. 		if first <= limit_value then
  23. 			sub = listup(a[1..a.size-1], limit_value - first)
  24. 			if sub.empty? then
  25. 				b = [[ first ]]
  26. 			else
  27. 				b =  sub.collect { |item| [ first ] + item }
  28. 			end
  29. 		end
  30.  
  31. 		# 先頭の値を除いたリストに対して探索
  32. 		c = listup(a[1..a.size-1], limit_value)
  33.  
  34. 		# ふたつをマージ
  35. 		b = b + c
  36.  
  37. 		# 候補の中から、合計値が一番大きいものを解として採用
  38. 		v_max = 0
  39. 		b.each { |item|
  40. 			v = sum(item)
  41. 			if v_max < v then
  42. 				ans = [ item ]
  43. 				v_max = v
  44. 			elsif v_max == v then
  45. 				ans.push item
  46. 			end
  47. 		}
  48. 	end
  49.  
  50. 	return ans
  51. end
  52.  
  53.  
  54.  
  55.  
  56. def test(a, limit)
  57. 	puts "** [#{a.join(',')}] <= #{limit}"
  58. 	listup(a, limit).each_with_index { |d, idx|
  59. 		puts "#{idx + 1} : [#{d.join(',')}]"
  60. 	}
  61. 	puts "-----------"
  62. end
  63.  
  64. test([6,10,100,8,4], 111)
  65. test([1, 2, 3, 4, 5], 5)
  66. test([1, 2, 3, 4, 5], 4)
  67. test([41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199], 195)
  68.  
Success #stdin #stdout 0.03s 7416KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
** [6,10,100,8,4] <= 111
1 : [6,100,4]
2 : [10,100]
-----------
** [1,2,3,4,5] <= 5
1 : [1,4]
2 : [2,3]
3 : [5]
-----------
** [1,2,3,4,5] <= 4
1 : [1,3]
2 : [4]
-----------
** [41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199] <= 195
1 : [41,47,107]
2 : [41,53,101]
3 : [41,71,83]
4 : [43,73,79]
5 : [47,59,89]
6 : [53,59,83]
-----------
https://ideone.com/ltHGmZ
http://q...content-available-to-author-only...e.jp/1386755073
language:
Ruby (ruby 2.5.5)
created:
10 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!