-
Notifications
You must be signed in to change notification settings - Fork 1
/
cb.go
98 lines (91 loc) · 2.19 KB
/
cb.go
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
package cb
import (
"math"
"github.com/catorpilor/leetcode/utils"
)
func assignBikes(workers, bikes [][]int) int {
nw, nb := len(workers), len(bikes)
if nw == 0 || nb == 0 {
return 0
}
res := math.MaxInt32
visited := make([]bool, len(workers))
dfs(&visited, bikes, workers, 0, 0, &res)
return res
}
func dfs(visited *[]bool, bikes, workers [][]int, wid, distance int, res *int) {
if wid >= len(workers) {
*res = utils.Min(*res, distance)
return
}
if distance > *res {
return
}
for j := 0; j < len(bikes); j++ {
if (*visited)[j] {
continue
}
(*visited)[j] = true
dfs(visited, bikes, workers, wid+1, distance+dis(bikes[j], workers[wid]), res)
(*visited)[j] = false
}
}
func dis(p1, p2 []int) int {
return utils.Abs(p1[0]-p2[0]) + utils.Abs(p1[1]-p2[1])
}
func useDp(workers, bikes [][]int) int {
nw, nb := len(workers), len(bikes)
if nw == 0 || nb == 0 {
return 0
}
res := math.MaxInt32
dp := make([][]int, nw+1)
// init dp
for i := range dp {
// there are 1<<nb states
// for example 3 bikes 000,001,010,100,101,111...etc.
dp[i] = make([]int, (1 << nb))
for j := 0; j < (1 << nb); j++ {
// not overflow
if numOfOnes(j) == nw {
dp[i][j] = math.MaxInt32 / 2
} else {
dp[i][j] = math.MaxInt32
}
}
}
dp[0][0] = 0
for i := 1; i <= nw; i++ {
for s := 1; s < (1 << nb); s++ {
for j := 0; j < nb; j++ {
if (s & (1 << j)) == 0 {
// bike j already be assigned
continue
}
// get prev state by just clear the jth bit in s
prev := s ^ (1 << j)
// ignore some states when nb > nw
// for example nw = 1, nb = 3 there are only 3 valid states 001, 010, 100
// we can just ignore the rest by checking the numOfOnes(s) == numOfWorkers
if dp[i-1][prev] == math.MaxInt32 {
break
}
// fmt.Printf("prev is: %d, dp[i-1][prev]: %d, i:%d, s: %d\n", prev, dp[i-1][prev], i, s)
dp[i][s] = utils.Min(dp[i][s], dp[i-1][prev]+dis(workers[i-1], bikes[j]))
if i == nw {
res = utils.Min(res, dp[i][s])
// fmt.Printf("all the worker are assigned, res:%d, dp[i][s]:%d\n", res, dp[i][s])
}
}
}
}
return res
}
func numOfOnes(i int) int {
var res int
for i > 0 {
i &= (i - 1)
res++
}
return res
}