先說說我為什么寫這些吧

• 當(dāng)程序猿太苦逼了，真的，時間久了，真沒有搬磚的成就感高，好歹人家能蓋棟樓（身材也能練得不錯），咱們指不定哪天來個熊孩子把硬盤格了就啥也沒了。
• 這學(xué)期明顯沒把心放在前端上……汗啊，將來還想吃著口飯呢，但是這學(xué)期絕對沒休息，只是忙了很多可能很多人認為無聊的事。
• 因為這學(xué)期無聊事太多了，耽誤了很多，也讓導(dǎo)師很失望，自己也很自卑，整理一下調(diào)調(diào)心態(tài)。
• 因為很多是針對作業(yè)的奇葩想法，所以，作業(yè)嘛，不糊弄就不是作業(yè)了，還希望大家多多批評。
• 興許因為哪篇文章能解決工作呢。
• 我想試試Markdown。

靚照一張

進入正題

后臺實現(xiàn)部分:

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 += "動態(tài)規(guī)劃,選擇物品"+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" 

前端實現(xiàn)部分:

• 輸入示例：{"n":10,"m":3,"w":[3,4,5],"v":[4,5,6]}其中n為背包容量，m為物品數(shù)量

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