企业官网建设流程全解析

算法详细实现：

package main

import "fmt"

/*
生活场景回溯算法 Go 实现合集

核心模板：
1. 做选择
2. 递归进入下一层
3. 撤销选择
4. 尝试其它选择

包含：
1. 聚餐座位安排（排列 + 约束）
2. 100元买礼物（组合 + 剪枝）
3. 房间分配（分组 + 约束）
*/

// ===============================
// 示例1：聚餐座位安排
// 4个人围桌坐，要求小明和小红不能相邻
// ===============================

func SeatArrangement() {
people := []string{"小明", "小红", "小刚", "小李"}
used := make([]bool, len(people))
path := []string{}
result := [][]string{}

var backtrack func()

valid := func(arr []string) bool {
for i := 0; i < len(arr)-1; i++ {
if (arr[i] == "小明" && arr[i+1] == "小红") ||
(arr[i] == "小红" && arr[i+1] == "小明") {
return false
}
}
return true
}

backtrack = func() {
// 结束条件：4个人全部安排
if len(path) == len(people) {
if valid(path) {
temp := append([]string{}, path...)
result = append(result, temp)
}
return
}

for i := 0; i < len(people); i++ {
if used[i] {
continue
}

// 做选择
used[i] = true
path = append(path, people[i])

// 递归探索
backtrack()

// 撤销选择
path = path[:len(path)-1]
used[i] = false
}
}

backtrack()

fmt.Println("座位方案：", len(result))
}

// ===============================
// 示例2：100元购买3件礼物
// 组合问题 + 金额剪枝
// ===============================

type Item struct {
Name string
Price int
}

func BuyGift() {
items := []Item{
{"玩偶", 40},
{"书", 30},
{"巧克力", 20},
{"杯子", 25},
{"耳机", 60},
{"积木", 50},
}

path := []Item{}
result := [][]Item{}

var backtrack func(int, int)

backtrack = func(start int, sum int) {

// 剪枝：超过预算直接返回
if sum > 100 {
return
}

// 选满3件
if len(path) == 3 {
temp := append([]Item{}, path...)
result = append(result, temp)
return
}

for i := start; i < len(items); i++ {

// 做选择
path = append(path, items[i])

// 下一层
backtrack(i+1, sum+items[i].Price)

// 撤销
path = path[:len(path)-1]
}
}

backtrack(0, 0)

fmt.Println("购买方案：", len(result))
}

// ===============================
// 示例3：房间分配
// 4个人住两个房间，每间2人
// 小明和小红不能同房
// ===============================

func RoomArrange() {

people := []string{"小明", "小红", "小刚", "小李"}

roomA := []string{}
roomB := []string{}

result := [][]string{}

var backtrack func(int)

check := func() bool {
for _, a := range roomA {
for _, b := range roomA {
if (a == "小明" && b == "小红") ||
(a == "小红" && b == "小明") {
return false
}
}
}
return true
}

backtrack = func(index int) {

if index == len(people) {

if len(roomA) == 2 && len(roomB) == 2 && check() {
result = append(result,
append([]string{}, roomA...),
append([]string{}, roomB...))
}

return
}

// 选择放入房间A
if len(roomA) < 2 {
roomA = append(roomA, people[index])
backtrack(index+1)
roomA = roomA[:len(roomA)-1]
}

// 选择放入房间B
if len(roomB) < 2 {
roomB = append(roomB, people[index])
backtrack(index+1)
roomB = roomB[:len(roomB)-1]
}
}

backtrack(0)

fmt.Println("分房方案：", len(result))
}

func main() {

fmt.Println("=== 聚餐座位 ===")
SeatArrangement()

fmt.Println("=== 买礼物 ===")
BuyGift()

fmt.Println("=== 房间分配 ===")
RoomArrange()
}