用coffee和socket.io实现的01背包算法

先说说我为什么写这些吧

• 当程序猿太苦逼了，真的，时间久了，真没有搬砖的成就感高，好歹人家能盖栋楼（身材也能练得不错），咱们指不定哪天来个熊孩子把硬盘格了就啥也没了。
• 这学期明显没把心放在前端上......汗啊，将来还想吃着口饭呢，但是这学期绝对没休息，只是忙了很多可能很多人认为无聊的事。
• 因为这学期无聊事太多了，耽误了很多，也让导师很失望，自己也很自卑，整理一下调调心态。
• 因为很多是针对作业的奇葩想法，所以，作业嘛，不糊弄就不是作业了，还希望大家多多批评。
• 兴许因为哪篇文章能解决工作呢。
• 我想试试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"

前端实现部分:

<html>
<head>
<meta charset="utf-8">
<script type="text/javascript" src="./jquery.min.js"></script>
<script type="text/javascript" src="./bootstrap.min.js"></script>
<script type="text/javascript" src="./socket.io/socket.io.js"></script>
<link rel="stylesheet" type="text/css" href="./bootstrap.min.css">
<script type="text/javascript">
$(function(){
    var url = window.location.protocol + "//" + window.location.host;
    var socket = io.connect(url);

     socket.on('connect', function () {
        $("#list").append('<li class="list-group-item">Connected</li>');
        socket.on('msg',function(data){
            $("#list").append($('<li class="list-group-item"></li>').text(data.time+">>"+data.text));
        })
        socket.on('disconnect',function(){
            $("#list").append('<li class="list-group-item">Disconnected</li>');
        })
    })

     $("#chat").keypress(function(e){
         if (e.which == 13) {
             e.preventDefault();
             socket.emit('msg',$("#chat").val());
             $("#list").append('<li class="list-group-item">'+$('#chat').val()+'</li>');

             $('#chat').val(" ");
         };
     })
})
</script>
</head>
<body>
<br>
<div class="container well">
    <ul class="list-group" id="list">
        <li class="list-group-item">输入示例：{"n":10,"m":3,"w":[3,4,5],"v":[4,5,6]}其中n为背包容量，m为物品数量</li>
    </ul>
    <div>
        <input type="text" class="form-control" id="chat">
    </div>
</div>
</body>
</html>