各种解背包问题

montecarlo

蒙特卡洛

import numpy as np

def solve(vlist,wlist,totalWeight,totalLength):
    ValListLen=np.power(2,totalLength)
    choiceList=np.arange(ValListLen,dtype=np.int32)
    np.random.shuffle(choiceList)
    choiceListLen=ValListLen//4*3
    ValList = np.zeros(choiceListLen,dtype=np.int32)
    for i in range(choiceListLen):
        i_tmp=choiceList[i]
        value=0
        weight=0
        for j in range(totalLength-1,-1,-1):
            j_tmp=np.power(2,j)
            div=i_tmp//j_tmp;
            i_tmp=i_tmp-div*j_tmp
            if div:
                value=value+vlist[j]
                weight=weight+wlist[j]
        if weight<=totalWeight:
           ValList[i]=value;
    return(ValList.max())
        
if __name__ == '__main__':
    v = [4,6,12,7]
    w = [1,2,3,2]
    weight = 6
    n = 4
    result = solve(v,w,weight,n)
    print(result)

backtrack

回溯

bestV=0
curW=0
curV=0
bestx=None

def solve_backtrack_asist(i,x,vlist,wlist,totalWeight,totalLength):
    global bestV,curW,curV,bestx
    if i>=totalLength:
        if bestV<curV:
            bestV=curV
            bestx=x[:]
    else:
        if curW+wlist[i]<=totalWeight:
            x[i]=1
            curW+=wlist[i]
            curV+=vlist[i]
            solve_backtrack_asist(i+1,x,vlist,wlist,totalWeight,totalLength)
            curW-=wlist[i]
            curV-=vlist[i]
        x[i]=0
        solve_backtrack_asist(i+1,x,vlist,wlist,totalWeight,totalLength)
    return bestV

def solve(vlist,wlist,totalWeight,totalLength):
    x=[0 for i in range(totalLength)]
    bestV=solve_backtrack_asist(0,x,vlist,wlist,totalWeight,totalLength)
    return bestV
    

if __name__ == '__main__':
    v = [4,6,12,7]
    w = [1,2,3,2]
    weight = 6
    n = 4
    bestV=solve(v,w,weight,n)
    print(bestV)

branch

分支限界

import numpy as np
import queue
import math
#value
def solve(vlist,wlist,totalWeight,totalLength):
    vec_len = 2**(totalLength+1) - 1#tree `s size
    vec_v = np.zeros(vec_len)
    vec_w = np.zeros(vec_len)
    vec_w[0]=totalWeight
    que = queue.Queue();
    que.put(0)
    best = 0
    while(not que.empty()):
        current = que.get()
        level = int(math.log(current+1,2))
        if(vec_v[current] > vec_v[best]):
            best = current
 
        left = 2*current+1#left child index
        right = 2*current+2#right child index
 
        if(left < vec_len and vec_w[current]-wlist[level] >= 0 and vec_v[current]+vlist[level] > vec_v[best] ):
            vec_v[left] = int(vec_v[current]+vlist[level])
            vec_w[left] = vec_w[current]-wlist[level]
            que.put(left)
        if(right < vec_len and sum(vlist[level+1:-1])+vec_v[current] > vec_v[best]):
            vec_v[right] = vec_v[current]
            vec_w[right] = vec_w[current]
            que.put(right)
    return int(vec_v[best])
 
if  __name__ == '__main__':
    w = [1,2,3,2]#weight
    v = [4,6,12,7]
    weight=6
    n=4
    result=solve(v,w,weight,n)
    print(result)

dynamic

动态规划

import numpy as np

def solve(vlist,wlist,totalWeight,totalLength):
    resArr = np.zeros((totalWeight)+1,dtype=np.int32)
    for i in range(0,totalLength):
        for j in range(totalWeight,0,-1):
            if wlist[i] <= j:
                resArr[j] = max(resArr[j],resArr[j-wlist[i]]+vlist[i])
    return resArr[-1]

if __name__ == '__main__':
    v = [4,6,12,7]
    w = [1,2,3,2]
    weight = 6
    n = 4
    result = solve(v,w,weight,n)
    print(result)

exhoustive

穷举

import numpy as np

def solve(vlist,wlist,totalWeight,totalLength):
    ValListLen=np.power(2,totalLength)
    ValList = np.zeros(ValListLen,dtype=np.int32)
    for i in range(ValListLen):
        i_tmp=i
        value=0
        weight=0
        for j in range(totalLength-1,-1,-1):
            j_tmp=np.power(2,j)
            div=i_tmp//j_tmp;
            i_tmp=i_tmp-div*j_tmp
            if div:
                value=value+vlist[j]
                weight=weight+wlist[j]
        if weight<=totalWeight:
           ValList[i]=value;
    return(ValList.max())
        
if __name__ == '__main__':
    v = [4,6,12,7]
    w = [1,2,3,2]
    weight = 6
    n = 4
    result = solve(v,w,weight,n)
    print(result)

memorandum

记事本

import numpy as np

def solve(vlist,wlist,totalWeight,totalLength):
    resArr = np.zeros((totalLength,totalWeight+1),dtype=np.int32)
    for i in range(0,totalLength):
        for j in range(1,totalWeight+1):
            if wlist[i] <= j:
                resArr[i,j] = max(resArr[i-1,j-wlist[i]]+vlist[i],resArr[i-1,j])
            else:
                resArr[i,j] = resArr[i-1,j]
    return resArr[-1,-1]

if __name__ == '__main__':
    v = [4,6,12,7]
    w = [1,2,3,2]
    weight = 6
    n = 4
    result = solve(v,w,weight,n)
    print(result)

main

对比时间

import backtrack
import branch
import dynamic
import exhoustive
import memorandum
import montecarlo

import time

epoch=10000

if __name__=='__main__':
    v = [4,6,12,7]
    w = [1,2,3,2]
    weight = 6
    n = 4
    
    time_start=time.time()
    for i in range(epoch):
        bestV=backtrack.solve(v,w,weight,n)
    time_end=time.time()
    print(bestV,time_end-time_start)
    
    time_start=time.time()
    for i in range(epoch):
        bestV=branch.solve(v,w,weight,n)
    time_end=time.time()
    print(bestV,time_end-time_start)
    
    time_start=time.time()
    for i in range(epoch):
        bestV=dynamic.solve(v,w,weight,n)
    time_end=time.time()
    print(bestV,time_end-time_start)
    
    time_start=time.time()
    for i in range(epoch):
        bestV=exhoustive.solve(v,w,weight,n)
    time_end=time.time()
    print(bestV,time_end-time_start)
    
    time_start=time.time()
    for i in range(epoch):
        bestV=memorandum.solve(v,w,weight,n)
    time_end=time.time()
    print(bestV,time_end-time_start)
    
    time_start=time.time()
    for i in range(epoch):
        bestV=montecarlo.solve(v,w,weight,n)
    time_end=time.time()
    print(bestV,time_end-time_start)