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