遡及法:最適なマウント問題

皆さん、こんにちは.私は連人です.今期は遡及法における最適積載問題について述べる.
簡単な言葉で言えば、2隻の船を与えて、1ロットの貨物を別々に積み込むように要求します.
この問題は「できるだけ最大積載で1隻の船を積み、残りの貨物でもう1隻を積む」ことを採用している.
これにより、問題を0-1リュックサックの問題に簡略化します.遡及法を用いて解空間を構築し,その後遍歴すればよい.考え方は簡単で、コードの注釈も詳しく書きました.

def traceback(depth):
    global n, goods, ship, best_arrange, now_arrange, best_load, now_load, remain

    if depth >= n:                 #       ，    
        if now_load > best_load:
            best_arrange = now_arrange
            best_load = now_load
        return

    remain -= goods[depth]         #              

    if now_load + goods[depth] <= ship:    #               
        now_arrange[depth] = 1             #                
        now_load += goods[depth]           #              
        traceback(depth+1)                 #       
        now_load -= goods[depth]           #           

    if now_load + remain > best_load:      #                              
        now_arrange[depth] = 0             #         
        traceback(depth+1)                 #        if      "  "，             

    remain += goods[depth]


def result_out():
    global best_arrange, best_load, ship, n, goods
    l = 0
    for i in range(0, n):
        if best_arrange[i] == 0:
            l += goods[i]
    if l > ship:
        print('    ')
    else:
        print('    ')
        print('      ：', end='')
        for i in range(0, n):
            if best_arrange[i] == 1:
                print(i, end=' ')
        print()
        print('      ：', end='')
        for i in range(0, n):
            if best_arrange[i] == 0:
                print(i, end=' ')


if __name__ == '__main__':
    n = 3                          #     
    goods = [40, 40, 10]           #   
    ship = 50                      #       
    best_arrange = [0, 0, 0]       #      
    now_arrange = [0, 0, 0]        #         
    best_load = 0                  #            
    now_load = 0                   #        
    remain = sum(goods)            #       
    traceback(0)
    result_out()

転載して出典を明記する.