-
Notifications
You must be signed in to change notification settings - Fork 10
/
Copy path01-01-knapsack.rb
125 lines (105 loc) · 3.1 KB
/
01-01-knapsack.rb
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
puts "Knapsack"
def knapsack(w, p, cap, len = w.length)
return 0 if len.zero? || cap <= 0
[knapsack(w, p, cap, len - 1), p[len - 1] + knapsack(w, p, cap - w[len - 1], len - 1)].max
end
p knapsack([1, 2, 3, 4], [5, 6, 7, 8], 4, 4)
def knapsack_dp(w, p, cap)
prev = (cap + 1).times.collect { 0 }
cur = (cap + 1).times.collect { 0 }
1.upto(w.length) do |len|
0.upto(cap) do |cap|
if w[len - 1] <= cap
cur[cap] = [prev[cap], p[len - 1] + prev[cap - w[len - 1]]].max
else
cur[cap] = prev[cap]
end
end
cur, prev = prev, cur
end
prev[cap]
end
p knapsack([1, 2, 3, 4], [5, 6, 7, 8], 4, 4)
puts "Equal subsets"
def can_partition(nums)
sum = nums.sum
return false if sum.odd?
can_partition_dp(nums, sum / 2)
end
def can_partition_r(nums, target, len = nums.length)
return false if target < 0
return target.zero? if len.zero?
can_partition_r(nums, target, len - 1) || can_partition_r(nums, target - nums[len - 1], len - 1)
end
def can_partition_dp(nums, target, len = nums.length)
prev = (1 + target).times.collect { false }
cur = (1 + target).times.collect { false }
prev[0] = true
1.upto(nums.length) do |len|
0.upto(target) do |target|
cur[target] = prev[target] || (nums[len - 1] <= target && prev[target - nums[len - 1]])
end
prev, cur = cur, prev
end
prev[target]
end
p can_partition [1, 2, 3, 6]
p can_partition [1, 2, 3, 5]
puts "Min subset difference"
def min_subset_diff(nums)
sum = nums.sum
found = can_partition_dp(nums, sum / 2)
sum - 2 * found
end
def can_partition_dp(nums, target, len = nums.length)
prev = (1 + target).times.collect { false }
cur = (1 + target).times.collect { false }
prev[0] = true
1.upto(nums.length) do |len|
0.upto(target) do |target|
cur[target] = prev[target] || (nums[len - 1] <= target && prev[target - nums[len - 1]])
end
prev, cur = cur, prev
end
target.downto(0).find { |x| prev[x] }
end
p min_subset_diff [1, 2, 3, 5]
p min_subset_diff [1, 2, 3, 6]
p min_subset_diff [1, 2, 3, 600]
puts "Count of subset sum"
def subset_count(nums, target, len = nums.length)
prev = (1 + target).times.collect { 0 }
cur = (1 + target).times.collect { 0 }
prev[0] = 1
1.upto(nums.length) do |len|
0.upto(target) do |target|
cur[target] = prev[target]
cur[target] += prev[target - nums[len - 1]] if nums[len - 1] <= target
end
prev, cur = cur, prev
end
prev[target]
end
p subset_count [1, 2, 2, 3, 4], 4
puts "Target sum"
def count_target_sum(nums, target, len = nums.length)
return 0 if len < 1
target_sum(nums, target - nums[len - 1], len - 1) + target_sum(nums, target + nums[len - 1], len - 1)
end
def count_target_sum(nums, target)
target = (nums.sum + target) / 2
prev = (1 + target).times.collect { 0 }
cur = (1 + target).times.collect { 0 }
prev[0] = 1
1.upto(nums.length) do |len|
0.upto(target) do |target|
cur[target] = prev[target]
cur[target] += prev[target - nums[len - 1]] if nums[len - 1] <= target
end
prev, cur = cur, prev
end
prev[target]
end
# P - S = T
# P + S = SUM
p count_target_sum [1, 2, 2, 3], 0