首页 > 其他 > 详细

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

时间:2014-07-21 13:25:12      阅读:341      评论:0      收藏:0      [点我收藏+]

先说说我为什么写这些吧

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

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

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

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

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

  • 我想试试Markdown。

    靓照一张

    bubuko.com,布布扣

    进入正题

    后台实现部分:

    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为物品数量


用coffee和socket.io实现的01背包算法,布布扣,bubuko.com

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

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

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!