先说说我为什么写这些吧

• 当程序猿太苦逼了，真的，时间久了，真没有搬砖的成就感高，好歹人家能盖栋楼（身材也能练得不错），咱们指不定哪天来个熊孩子把硬盘格了就啥也没了。

• 这学期明显没把心放在前端上……汗啊，将来还想吃着口饭呢，但是这学期绝对没休息，只是忙了很多可能很多人认为无聊的事。

• 因为这学期无聊事太多了，耽误了很多，也让导师很失望，自己也很自卑，整理一下调调心态。

• 因为很多是针对作业的奇葩想法，所以，作业嘛，不糊弄就不是作业了，还希望大家多多批评。

• 兴许因为哪篇文章能解决工作呢。

• 我想试试Markdown。

  靓照一张

  进入正题

  后台实现部分:

  io = require “socket.io”
  http = require “http”
  fs = require “fs”
  express = require “express”
  mime = require “mime”
  app = express()

  server = http.createServer app
  server.listen 8080
  console.log “Listening 8080”

  app.get “/“,(req,res)->

  path = "#{__dirname}/console.html"
  res.writeHead 200,"Content-Type":mime.lookup(path)
  res.end fs.readFileSync path

  app.get “/jquery.min.js”,(req,res)->

  path = "#{__dirname}/jquery.min.js"
  res.writeHead 200,"Content-Type":mime.lookup(path)
  res.end fs.readFileSync path

  app.get “/bootstrap.min.js”,(req,res)->

  path = "#{__dirname}/bootstrap.min.js"
  res.writeHead 200,"Content-Type":mime.lookup(path)
  res.end fs.readFileSync path

  app.get “/bootstrap.min.css”,(req,res)->

  path = "#{__dirname}/bootstrap.min.css"
  res.writeHead 200,"Content-Type":mime.lookup(path)
  res.end fs.readFileSync path

  getCurrentTime = ->
  d = new Date()
  return “#{d.getFullYear()}-#{d.getMonth()+1}-#{d.getDate()} #{d.getHours()}:#{d.getMinutes()}:#{d.getSeconds()}”

  class dynamicPack

  pack:(data)->
      c=[]
      i=0
      j=0
      while i<data.m+1
          c[i]=[]
          c[i][0]=0
          i++
      while j<data.n+1
          c[0][j]=0
          j++
      i=1
      while i<data.m+1
          j=1
          while j<data.n+1
              if data.w[i-1]<=j
                  if c[i-1][j]<c[i-1][j-data.w[i-1]]+data.v[i-1]
                      c[i][j]=c[i-1][j-data.w[i-1]]+data.v[i-1]
                  else 
                      c[i][j]=c[i-1][j]
              else c[i][j] = c[i-1][j]
              j++
          i++
      return c;
  print:(c,data)->
      x = []
      i = data.m
      n = data.n
      str = ""
      #console.log c[i][m]
      while i>0
          if  c[i][n] > c[i-1][n]
              x[i-1] = 1
              n -= data.w[i-1]
          else x[i-1] = 0
          i--
      i= 0
      count = 0
      while i<data.m
          count += x[i]*data.v[i]
          str += (i+1)+"," if x[i]!=0
          i++             
      return str+"共计价值#{count}"

  class knapPack

  pack : (data)->
      @v = data.v
      @w = data.w
      @m = data.m
      @n = data.n
      @cw = 0
      @cv = 0
      @put = []
      @bestp = 0
  
      temp_order = 0;
      temp = 0
      perp = []
      i=0
      while i<@m
          perp[i] = @v[i]/@w[i] 
          @put[i] = 0;
          i++
      console.log perp
      i=0
      while i<@m
          j=i+1
          while j<@m
              if perp[i]<perp[j]
                  temp = @v[i]
                  @v[i] = @v[j]
                  @v[j] = temp
  
                  temp = @w[i]
                  @w[i] = @w[j]
                  @w[j] = temp
              j++
          i++
  backtrack : (i)->
      console.log i
      @bound i
      if i>@m
          @bestp = @cv
          return
      if @cw+@w[i]<=@n
          @cw+=@w[i]
          @cv+=@v[i]
          @put[i]=1
          @backtrack(i+1)
          @cw-=@w[i]
          @cv-=@v[i]
      if @bound(i+1)>@bestp
          @backtrack(i+1)
  bound :(i)->
      leftw = @n - @cw
      b = @cv
      while i<=@m and @w[i]<=leftw
          leftw -= @w[i]
          b += @v[i]
          i++
      b+=@v[i]/@w[i]*leftw if i<@m
      return b
  print :(data)->
      @pack(data)
      console.log @w
      console.log @v
      @backtrack(0)
      console.log @put 
      return @bestp

  dask = (msg)->

  answer = ""
  data = JSON.parse msg
  console.log data
  
  d = new dynamicPack()
  console.log d.pack(data)
  answer += "动态规划,选择物品"+d.print d.pack(data),data
  return answer

  kask = (msg)->

  answer = ""
  data = JSON.parse msg
  console.log data
  
  k = new knapPack()
  answer += "分支限界,最优解"+k.print data
  return answer

  io.listen(server).on “connection”,(socket)->

  socket.on "msg",(msg)->
      ##console.log msg
      socket.emit "msg",{time:getCurrentTime(),text:"calculating..."}
      socket.emit "msg",{time:getCurrentTime(),text:dask(msg)}
      socket.emit "msg",{time:getCurrentTime(),text:kask(msg)}
      ##socket.broadcast.emit "msg",data
  
  console.log "#{getCurrentTime()}:Connected"

  前端实现部分:

  
  
  
  
  
  
  
  
  
  
  

  • 输入示例：{"n":10,"m":3,"w":[3,4,5],"v":[4,5,6]}其中n为背包容量，m为物品数量

  
  

原文：http://my.oschina.net/gongbaodd/blog/293129