为了账号安全,请及时绑定邮箱和手机立即绑定

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

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

Go
慕姐4208626 2023-06-12 16:35:17
问题:给定一个非重复正整数数组,表示“n”个人的穿越时间。这n个人站在桥的一侧。Bridge 一次最多可容纳两个人。两人过桥时,必须以较慢者的步调走。找出所有人可以过桥的最短总时间。我无法找到关于如何为“n”个人扩展它的模式。但不知何故,我设法找到了 4 个人的案子。有人可以帮我弄这个吗。我是 Golang 的新手,我被这个问题困住了。package mainimport (    "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/ObTVA8gk0mgConfig.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”个人。那么在给定约束的情况下,他们过桥的最短时间是多少。
查看完整描述

2 回答

?
萧十郎

TA贡献1815条经验 获得超13个赞

我认为原始问题比陈述的问题更有趣(是的,“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 = 15

x = [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},+{...} 表示在所需方向上交叉,-{...} 在相反的方向

逻辑:

  1. 如果 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]] 的原始问题,可以通过应用相同的逻辑并对交叉时间求和来迭代求解

查看完整回答
反对 回复 2023-06-12
?
慕勒3428872

TA贡献1848条经验 获得超6个赞

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


person:

  person_1: 2

  person_2: 1

  person_3: 5

  person_4: 8

  person_5: 9

你的算法看起来很复杂。


例如,


package main


import (

    "fmt"

    "sort"

)


func minCrossingTime(people []int) int {

    sort.Slice(people, func(i, j int) bool {

        return people[i] > people[j]

    })

    min := 0

    for i := 0; i < len(people); i += 2 {

        min += people[i]

    }

    return min

}


func main() {

    people := []int{2, 1, 5, 8, 9}

    fmt.Println(len(people), people)

    crossingTime := minCrossingTime(people)

    fmt.Println(len(people), people)

    fmt.Println(crossingTime)

}

游乐场:https://play.golang.org/p/pXdGcinwxr-


输出:


5 [2 1 5 8 9]

5 [9 8 5 2 1]

15


查看完整回答
反对 回复 2023-06-12
  • 2 回答
  • 0 关注
  • 163 浏览
慕课专栏
更多

添加回答

举报

0/150
提交
取消
意见反馈 帮助中心 APP下载
官方微信