排序算法产生不正确结果

知识点掌握了，还需要不断练习才能熟练运用。下面golang学习网给大家带来一个Golang开发实战，手把手教大家学习《排序算法产生不正确结果》，在实现功能的过程中也带大家重新温习相关知识点，温故而知新，回头看看说不定又有不一样的感悟！

我有一个包含数据行的 csv。每行由一个 amount_of_apples 和多个 steps 组成。 amount_of_apples 是房间中苹果的总数，steps 是到房间的距离（以步数为单位）。

amount_of_apples, steps
6,  99
9,  45
15, 88
32, 115
6,  52
74, 227
2,  56
17, 14
9,  49

我想知道如果我每天只能走 max_steps，例如 100，我最多可以收集多少个苹果。

我当前的解决方案包括按重量对房间进行排序，然后根据重量访问每个房间。

权重:=苹果数/步数

所以我会先去 1 步外有 59 个苹果的房间，然后再去 3 步外有 51 个苹果的房间。然后，我会访问列表中的下一个房间，其步数小于剩余步数，并继续，直到用完房间或步数。

当前解决方案（返回 26 ，这是不正确的）：

// sort rooms by weight ratio of apples to steps
sort.SliceStable(rooms, func(i, j int) bool {
        currRatio := rooms[i].numberOfApples/ rooms[i].steps
        nextRatio := rooms[j].numberOfApples / rooms[i].steps
        return currRatio > nextRatio
    })

var results []Room
    var index int
    var count float64
    var steps int
    for steps < maxSteps {
     step += rooms[index].steps
        if steps > maxSteps {
            break
        }
        results = append(results, rooms[index])
        count += rooms[index].numberOfApples
        index += 1
    }

log.Printf("The max number of apples that can be collected in %vsteps is %v", maxSteps, count)

但是，我认为这不是正确的解决方案。

p.s 我们可以假设，一旦访问了一个房间并收集了苹果，您就会神奇地传送回起点。因此回溯不会浪费任何步骤。

正确答案

这个已经重新开放了，所以我不妨看看用 golang 编程是什么样的。

这仅返回最大数量，而不返回您访问过的房间。如何查找房间请见https://stackoverflow.com/a/72984102/585411。

func findMaxApples(maxSteps int, rooms []Room) int {
        // We will use "fake rooms to indicate the results of our trip.
        fringe := []Room{
                {
                        steps:          0,
                        numberOfApples: 0,
                },
        }

        for _, room := range rooms {
                withRoom := []Room{}
                for _, prevPath := range fringe {
                        if prevPath.steps+room.steps <= maxSteps {
                                withRoom = append(withRoom, Room{steps: prevPath.steps + room.steps, numberOfApples: prevPath.numberOfApples + room.numberOfApples})
                        }
                }
                
                newFringe := []Room{}
                i := 0
                j := 0 
                for (i < len(fringe)) && (j < len(withRoom)) {
                        chooseFringe := false
                        if fringe[i].steps < withRoom[j].steps {
                                chooseFringe = true 
                        } else if withRoom[j].steps < fringe[i].steps {
                                chooseFringe = false
                        } else if fringe[i].numberOfApples < withRoom[j].numberOfApples {
                                chooseFringe = false
                        } else {
                                chooseFringe = true
                        }
                        
                        if chooseFringe {
                                for j < len(withRoom) && withRoom[j].numberOfApples <= fringe[i].numberOfApples {
                                        j++
                                }
                                newFringe = append(newFringe, fringe[i])
                                i++
                        } else {
                                for i < len(fringe) && fringe[i].numberOfApples <= withRoom[j].numberOfApples {
                                        i++
                                }
                                newFringe = append(newFringe, withRoom[j])
                                j++
                        }
                }
               
                for i < len(fringe) {
                        newFringe = append(newFringe, fringe[i])
                        i++
                }

                for j < len(withRoom) {
                        newFringe = append(newFringe, withRoom[j])
                        j++
                }

                fringe = newFringe
        }

        return fringe[len(fringe)-1].numberOfApples
}

今天关于《排序算法产生不正确结果》的内容就介绍到这里了，是不是学起来一目了然！想要了解更多关于的内容请关注golang学习网公众号！