动态规划
题目一：
一群朋友组队玩游戏，至少有5组人，一组至少2人，要求：
1.每2个人组一队或者3个人组一队，每个人只能加到一个队伍里，不能落单
2.2人队和3人队各自的队伍数均不得少于1，队伍中的人不能来自相同组
3.随机组队，重复执行程序得到的结果不一样，总队伍数也不能一样
4.必须有注释
注：要同时满足条件1-4
举例：
GroupList=[#小组列表
['少华','少平','少军','少安','少康'],
['福军','福堂','福民','福平','福心']
['小明','小红','小花','小丽','小强'],
['大壮','大力','大1','大2','大3'],
['阿花','阿朵','阿蓝','阿紫','阿红'],
['A','B','C','D','E'],
['一','二','三',' 四','五'],
]
输入：GroupList
示例输出:[小强 大3][阿红 E][五 少华][福军 小明][大壮 阿花][A 一][少平 福堂][小红 大力][阿朵 B][二 少军][福民 小花][大1 阿蓝][C 三][少安 福平 小丽][大2 阿紫 D][四 少康 福心]
package main
import (
"errors"
"fmt"
"math/rand"
"time"
)
var (
minGroups = 5
minGroupPeople = 2
maxGroups = 35 / minGroupPeople
maxGroupPeople = 35 / minGroups
twoPeopleGroups = 0
threePeopleGroups = 0
totalGroups = 0
//记录总队伍数 满足总队伍数不能一样
totalGroupsList []int
//已分配队伍的人
inGroupPeoples []*Player
//分组结果
resultGroup [][]*Player
resultStringGroup [][]string
)
var groupList = [][]string{
{"少华", "少平", "少军", "少安", "少康"},
{"福军", "福堂", "福民", "福平", "福心"},
{"小明", "小红", "小花", "小丽", "小强"},
{"大壮", "大力", "大1", "大2", "大3"},
{"阿花", "阿朵", "阿蓝", "阿紫", "阿红"},
{"A", "B", "C", "D", "E"},
{"一", "二", "三", "四", "五"},
}
type Player struct {
GroupId int
Index int
Name string
}
func NewPlayer(groupId int, index int, name string) *Player {
return &Player{
GroupId: groupId,
Index: index,
Name: name,
}
}
// 已知三人一组的组数 获取二人一组的组数
func getTwoPeopleGroupsNumber(threePeopleGroups int) int {
if (35-threePeopleGroups*3)%2 == 0 {
return (35 - threePeopleGroups*3) / 2
} else {
return 0
}
}
// 尝试分配 两人一组 和三人一组 每组有多少人
func getGroupNumber() {
for {
//fmt.Println("getGroupNumber")
threePeopleGroups = rand.Intn(maxGroups-minGroups+1) + minGroups
twoPeopleGroups = getTwoPeopleGroupsNumber(threePeopleGroups)
if twoPeopleGroups < 1 {
continue
}
fmt.Println("twoPeopleGroups: ", twoPeopleGroups)
fmt.Println("threePeopleGroups: ", threePeopleGroups)
found := false
for _, v := range totalGroupsList { //总队伍数不能一样
if v == twoPeopleGroups+threePeopleGroups {
found = true
break
}
}
//得到正确的组数 终止循环
if !found {
break
}
}
}
// 随机抽取一个人
func rangPlayer() *Player {
groupId := 0
index := 0
for {
groupId = rand.Intn(7)
index = rand.Intn(5)
//fmt.Println("index:", index, " group:", groupId)
found := false
for _, v := range inGroupPeoples { //是否被抽走
if v.GroupId == groupId && v.Index == index {
found = true
break
}
}
if !found {
break
}
}
//fmt.Println(groupList[groupId][index], " 随机groupId:", groupId, "随机index:", index)
p := NewPlayer(groupId, index, groupList[groupId][index])
inGroupPeoples = append(inGroupPeoples, p)
return p
}
// 创建 2 人分组
func getTwoPeopleGroups() (group []*Player, err error) {
a := rangPlayer()
var b *Player
for groupId := 0; groupId < 7; groupId++ {
for index := 0; index < 5; index++ {
found := false
for _, v := range inGroupPeoples { //是否被抽走
if v.GroupId == groupId && v.Index == index {
found = true
break
}
}
if !found {
if a.GroupId != groupId { //不能同组
b = NewPlayer(groupId, index, groupList[groupId][index])
break
}
}
}
}
//fmt.Println(a.Name)
if b == nil {
fmt.Println("方案不可用")
err = errors.New("方案不可用")
return
}
inGroupPeoples = append(inGroupPeoples, b)
group = append(group, b)
inGroupPeoples = append(inGroupPeoples, a)
group = append(group, a)
return
}
// 创建 3 人队伍
func getThreePeopleGroups() (group []*Player, err error) {
a := rangPlayer()
var b *Player
var c *Player
for groupId := 0; groupId < 7; groupId++ {
for index := 0; index < 5; index++ {
found := false
for _, v := range inGroupPeoples { //是否被抽走
if v.GroupId == groupId && v.Index == index {
found = true
break
}
}
if !found {
if a.GroupId != groupId { //是否同组
b = NewPlayer(groupId, index, groupList[groupId][index])
break
}
}
}
}
for groupId := 0; groupId < 7; groupId++ {
for index := 0; index < 5; index++ {
found := false
for _, v := range inGroupPeoples { //是否被抽走
if v.GroupId == groupId && v.Index == index {
found = true
break
}
}
if !found {
if a.GroupId != groupId && b.GroupId != groupId {
c = NewPlayer(groupId, index, groupList[groupId][index])
break
}
}
}
}
//fmt.Println(a.Name)
if b == nil {
fmt.Println("方案有问题")
err = errors.New("方案有问题")
return
}
if c == nil {
fmt.Println("方案有问题")
err = errors.New("方案有问题")
return
}
inGroupPeoples = append(inGroupPeoples, c)
group = append(group, c)
inGroupPeoples = append(inGroupPeoples, b)
group = append(group, b)
inGroupPeoples = append(inGroupPeoples, a)
group = append(group, a)
return
}
// 完整一次分钟过程
func makeGroup() {
fmt.Println(totalGroupsList)
getGroupNumber()
var err error = nil
var list []*Player
//三人队伍加入结果
for i := 0; i < threePeopleGroups; i++ {
//fmt.Println("三人队第", i+1, "组")
var stringList = []string{}
list, err = getThreePeopleGroups()
if err != nil {
//置空
inGroupPeoples = []*Player{}
resultGroup = [][]*Player{}
resultStringGroup = [][]string{}
break
}
for _, p := range list {
//fmt.Println(p.Name)
stringList = append(stringList, p.Name)
}
resultGroup = append(resultGroup, list)
resultStringGroup = append(resultStringGroup, stringList)
}
//二人队伍加入结果
for i := 0; i < twoPeopleGroups; i++ {
if err != nil {
break
}
var stringList2 = []string{}
//fmt.Println("二人队第", i+1, "组")
list, err = getTwoPeopleGroups()
if err != nil {
//置空
inGroupPeoples = []*Player{}
resultGroup = [][]*Player{}
resultStringGroup = [][]string{}
break
}
// fmt.Println("二人队第", i+1, "组")
for _, p := range list {
stringList2 = append(stringList2, p.Name)
}
resultGroup = append(resultGroup, list)
resultStringGroup = append(resultStringGroup, stringList2)
}
if err != nil {
fmt.Println("error2")
makeGroup()
return
}
//打印最终结果
// for i := 0; i < len(resultGroup); i++ {
// fmt.Println("第", i+1, "组---", len(resultGroup[i]), "人队")
// for _, p := range resultGroup[i] {
// fmt.Println(p.Name)
// }
// }
fmt.Println(resultStringGroup)
fmt.Println("---end---")
return
}
func main() {
rand.Seed(time.Now().UnixNano())
//分三次组
for i := 0; i < 3; i++ {
fmt.Println("第", i+1, "次分组")
fmt.Println("-----")
makeGroup()
//置空
inGroupPeoples = []*Player{}
totalGroupsList = append(totalGroupsList, twoPeopleGroups+threePeopleGroups)
resultGroup = [][]*Player{}
resultStringGroup = [][]string{}
}
}