Bit full search with Go

package main
import(
  "fmt"
  "bufio"
  "os"
  "strconv"
  "strings"
  "go/types"
  "go/token"
)
var rdr=bufio.NewReaderSize(os.Stdin,10000000)
func readLine()string{
  l,_,_:=rdr.ReadLine()
  return string(l)
}
func readInts()[]int{
  s:=strings.Split(readLine()," ")
  res:=[]int{}
  for i:=0;i<len(s);i++{
    i,_:=strconv.Atoi(s[i])
    res=append(res,i)
  }
  return res
}
func chmax(x,y int)int{if x>=y{return x}else{return y}}
func contains(x int,sl []int)bool{
  res:=false
  for i:=0;i<len(sl);i++{
    if sl[i]==x{
      res=true
      break
    }
  }
  return res
}
func main(){
  tmp:=readInts()
  n,m:=tmp[0],tmp[1]
  A:=readInts()
  B:=[]int{}
  I:=[][]int{}
  for i:=0;i<m;i++{
    tmp:=readInts()
    B=append(B,tmp[0])
    I=append(I,tmp[2:])
    for j:=0;j<tmp[1];j++{
      I[i][j]--
    }
  }
  //fmt.Println(n,A)
  //fmt.Println(B)
  //fmt.Println(I)
  ans:=0
  for bits:=0;bits<(1<<uint64(n));bits++{
    score:=0
    combo:=[]int{}
    for i:=0;i<n;i++{
      if (bits>>uint64(i))&1==1{
        score+=A[i] //The score of the person
        combo=append(combo,i)
      }
    }
    if len(combo)>9{
      continue
    }
    cnt:=0
    //bonus:=0
    for i:=0;i<m;i++{
      cnt=0
      for j:=0;j<len(combo);j++{
        if contains(combo[j],I[i]){
          cnt++
        }
      }
      if cnt>=3{
        score+=B[i]
        //bonus+=B[i]
      }
    }
    //if score==6100{fmt.Println("score",score,"combo",combo,"cnt",cnt,"B[i]",bonus)}
    ans=chmax(ans,score)
  }
  fmt.Println(ans)
}

Recommended Posts