使用 Go 的“n”人的桥梁和火炬问题

Question

问题：给定一个非重复正整数数组，表示“n”个人的穿越时间。这n个人站在桥的一侧。Bridge 一次最多可容纳两个人。两人过桥时，必须以较慢者的步调走。找出所有人可以过桥的最短总时间。

我无法找到关于如何为“n”个人扩展它的模式。但不知何故，我设法找到了 4 个人的案子。有人可以帮我弄这个吗。我是 Golang 的新手，我被这个问题困住了。

package main

import (

    "fmt"

    "io/ioutil"

    "log"

    "os"

    "sort"

    "gopkg.in/yaml.v2"

)

type conf struct {

    Person []map[string]float32 `yaml:"person"`

}

func (c *conf) getConf() *conf {

    filename := os.Args[1]                     // Taking file input

    yamlFile, err := ioutil.ReadFile(filename) // Yaml parse

    if err != nil {

        log.Printf("yamlFile.Get err   #%v ", err)

    }

    err = yaml.Unmarshal(yamlFile, c)

    if err != nil {

        log.Fatalf("Unmarshal: %v", err)

    }

    return c

}

func main() {

    var c conf  // Object of struct conf

    c.getConf() // calling getConf function

    // Sorting the current conf map

    n := map[float32][]string{} // Map to store current conf map

    var a []float32             // Store values from conf map

    for k, v := range c.Person {

        v := float32(v)

        fmt.Println(k, v)

        n[v] = append(n[v], k)

    }

    for k := range n {

        a = append(a, k)

    }

    // Converting float32 as float64 in order to sort the values in conf map

    float32AsFloat64Values := make([]float64, len(a))

    for i, val := range a {

        float32AsFloat64Values[i] = float64(val)

    }

    sort.Float64s(float32AsFloat64Values)

    for i, val := range float32AsFloat64Values {

        a[i] = float32(val)

    }

    var time float32

    fmt.Printf("\n%v\n", a)

    for _, k := range a {

        min1 := a[0]

        min2 := a[1]

        min3 := a[2]

游乐场：https://play.golang.org/p/ObTVA8gk0mg

Config.yaml 是：

person:
  person_1: 2
  person_2: 1
  person_3: 5
  person_4: 8
  person_5: 9

可以将其运行为：'go run main.go config.yaml'。我的情况是此 yaml 中可能有 4,5 或“n”个人。那么在给定约束的情况下，他们过桥的最短时间是多少。

Answer 1

我认为原始问题比陈述的问题更有趣（是的，“Bridge and Torch”问题中必须有一个 Torch！）。基于维基百科的描述，例如，四个人在夜里来到一条河边。有一座狭窄的桥，但一次只能容纳两个人。他们只有一支手电筒，因为是晚上，过桥时必须使用手电筒。A 1 分钟过桥，B 2 分钟过桥，C 5 分钟过桥，D 8 分钟过桥。两个人一起过桥的时候，一定要跟着慢的人走。问题是，如果火炬只持续15分钟，他们能全部过桥吗？当然，在我们的例子中，有 N 个人而不是四个人，他们过桥所花的时间不定，但故事的其余部分是相同的。这是实现：import (    "fmt"    "sort")func minCrossingTime(x []int) int {    if len(x) == 1 {        return x[0]    }    sort.Ints(x)    t := 0    a, b := x[0], x[1]    x = x[2:]    for len(x) >= 2 {        n := len(x)        c, d := x[n-2], x[n-1]        x = x[:n-2]        t1 := 2*b + a + d        t2 := d + c + 2*a        if t1 < t2 {            t += t1        } else {            t += t2        }    }    if len(x) == 1 {        c := x[0]        t += a + b + c    } else {        t += b    }    return t}func main() {    x1 := []int{1, 2, 5, 8}    fmt.Printf("x = %x, time = %d\n", x1, minCrossingTime(x1))    x2 := []int{3, 8, 1, 6, 2, 9}    fmt.Printf("x = %x, time = %d\n", x2, minCrossingTime(x2))}输出：x = [1 2 5 8], time = 15x = [1 2 3 6 8 9], time = 27注意：第一个例子 [1 2 5 8] 直接来自维基百科，所以答案是肯定的，他们可以在 15 分钟内穿过关键思想：释义：令 X = [X1,X2,...,XN] 为交叉时间的排序数组，其中 X1 最快，XN 最慢让我们将 XI 和 XJ 这对人交叉表示为 {XI,XJ}，XK 人交叉为 {XK}，+{...} 表示在所需方向上交叉，-{...} 在相反的方向逻辑：如果 N < 4 问题很简单：N = 1 => t = X1 (+{X1})N = 2 => t = X2 (+{X1,X2})N = 3 => t = X1 + X2 + X3 (+{X1,X2} -{X1} + {X1,X3})如果 N >= 4 考虑以下问题：如何让两个最慢的人（并且只有他们）过桥并在最短的时间内带回火炬。有两种“好”的方法，时间 t1 = X1 + 2*X2 + XN(+{X1,X2} -{X1} +{X[N-1],XN} -{X2}) 和 (+ t2 = 2*X1 + X[N-1] + XN{X1,X[N- 1]} -{X1} +{X1,XN} -{X1}), 所以我们从这两个中选择最好的（最小的）现在最慢的两个已经过桥，火炬在它开始的同一侧，所以我们剩下 X' = [X1, X2, ..., X[N-2]] 的原始问题，可以通过应用相同的逻辑并对交叉时间求和来迭代求解

Answer 2

问题：给定一个非重复正整数数组，表示“n”个人的穿越时间。这n个人站在桥的一侧。Bridge 一次最多可容纳两个人。两人过桥时，必须以较慢者的步调走。找出所有人可以过桥的最短总时间。person:&nbsp; person_1: 2&nbsp; person_2: 1&nbsp; person_3: 5&nbsp; person_4: 8&nbsp; person_5: 9你的算法看起来很复杂。例如，package mainimport (&nbsp; &nbsp; "fmt"&nbsp; &nbsp; "sort")func minCrossingTime(people []int) int {&nbsp; &nbsp; sort.Slice(people, func(i, j int) bool {&nbsp; &nbsp; &nbsp; &nbsp; return people[i] > people[j]&nbsp; &nbsp; })&nbsp; &nbsp; min := 0&nbsp; &nbsp; for i := 0; i < len(people); i += 2 {&nbsp; &nbsp; &nbsp; &nbsp; min += people[i]&nbsp; &nbsp; }&nbsp; &nbsp; return min}func main() {&nbsp; &nbsp; people := []int{2, 1, 5, 8, 9}&nbsp; &nbsp; fmt.Println(len(people), people)&nbsp; &nbsp; crossingTime := minCrossingTime(people)&nbsp; &nbsp; fmt.Println(len(people), people)&nbsp; &nbsp; fmt.Println(crossingTime)}游乐场：https://play.golang.org/p/pXdGcinwxr-输出：5 [2 1 5 8 9]5 [9 8 5 2 1]15