Pythonでナップサック問題を総当たりで解く

今回の概要

講義でナップサック問題を解く必要があったのでプログラムを用いて最適解を求めるものを作りました。 ナップサック問題を解く方法は貪欲法、吝嗇法(りんしょくほう)など色んな方法で解くことができるのですが、最適解を出すために今回は総当たりで解くことにしました。

ソースコード

main.py

# coding: utf-8
import itertools
import culculate

#それぞれのデータ
num = {1,2,3,4,5,6,7,8}
max_price = 0  #最高の価格
best_weight = 0 #制限重量内での価値が一番高い時のバッグ内重量
best_combi = [] #最適な組み合わせを保存
string = [] #すべての場合のコンビネーションをstring+数で保存

#numからコンビネーションのリストを作成
i = 0
for i  in num :
    string = "string" + str(i) 
    string = list(itertools.combinations(num, i))
    print("荷物"+str(i)+"つの時の探索開始")
    printer = culculate.round_robin(string,i)
    print("荷物"+str(i)+"つの時の探索終了")
    if printer[0] == 0 or printer[1] == [] :
        print("全ての場合で重量オーバー\n")
    else :
        print("荷物"+str(i)+"つの時の最大の価格は"+ str(printer[0]))
        print("その時の組み合わせは"+str(printer[1])+"\n")
        if max_price <= printer[0] :
            max_price = printer[0]
            best_combi = printer[1]
            best_weight = printer[2]
print("総当たりによる解は荷物の組み合わせ" + str(best_combi) + "の時に")
print("重さ：" + str(best_weight)+ "\t価値：" + str(max_price))
# print ("価値 "+ str(max_price))

culculate.py

# coding: utf-8
# cp は リストの長さに合わせて変わる変数
def round_robin(string, cp) :
    num = {1,2,3,4,5,6,7,8}
    weight = [3,6,5,4,8,5,3,4]
    price = [7,12,9,7,13,8,4,5]
    max_price = 0  #最高の価格
    best_weight =0 #制限重量内での価値が一番高い時のバッグ内重量
    limit_weight = 25 #制限重量
    bag_price = 0 #バッグ内の価値
    bag_weight = 0 #バッグ内の重量
    cnt = 0            #リストの1つあたりの長さに応じて処理するためのカウント変数
    best_combi = [] #最適な組み合わせを保存
    
    for num in string :
        print num
        for number in num : 
            print number
            bag_weight += weight[number-1]
            bag_price += price[number -1]
            print "重さ => " + str(bag_weight)
            print "価格 => " + str(bag_price)
            cnt += 1
            if max_price < bag_price and bag_weight <= limit_weight and cnt == cp :
                max_price = bag_price
                best_combi = num 
                best_weight = bag_weight
                print "価値更新 => " + str(max_price)
            if cnt >= cp : #ここはstringの数字の部分
                bag_weight = 0
                bag_price = 0
                cnt =0
    return [max_price, best_combi,best_weight]

実行結果 

荷物1つの時の探索開始

(1,)
1
重さ => 3
価格 => 7
価値更新 => 7

(2,)
2
重さ => 6
価格 => 12
価値更新 => 12

(3,)
3
重さ => 5
価格 => 9

(4,)
4
重さ => 4
価格 => 7

(5,)
5
重さ => 8
価格 => 13
価値更新 => 13

(6,)
6
重さ => 5
価格 => 8

(7,)
7
重さ => 3
価格 => 4

(8,)
8
重さ => 4
価格 => 5

荷物1つの時の探索終了
荷物1つの時の最大の価格は13
その時の組み合わせは(5,)

------途中省略---------

荷物8つの時の探索開始

(1, 2, 3, 4, 5, 6, 7, 8)
1
重さ => 3
価格 => 7

2
重さ => 9
価格 => 19

3
重さ => 14
価格 => 28

4
重さ => 18
価格 => 35

5
重さ => 26
価格 => 48

6
重さ => 31
価格 => 56

7
重さ => 34
価格 => 60

8

重さ => 38
価格 => 65

荷物8つの時の探索終了

全ての場合で重量オーバー

総当たりによる解は荷物の組み合わせ(1, 2, 3, 5, 7)の時に
重さ：25 価値：45
総当たりの総数は255

このような感じになりますが、出力情報がを多すぎため実行結果はかなり長くなるので もし使うならmain.pyの出力部分をいじって出力を減らすことをおススメします。 20の荷物情報で試したところ出力は200MByteちょっとになりました...笑

コードの解説

culculateに解かせたい問題情報を配列で渡しておきます。(荷物番号,重さ,価値)=(num[i],weight[i],price[i])でそれぞれが対応しています。こうすることで3つの情報を1つの荷物情報としてまとめていますが、もしかしたらこれより効率の良いやり方があるかもしれません。

import itertools でインポートしているのはpythonの組み合わせ、順列のライブラリです。itertools.combinations(x,y)で『xの配列の中からyの組み合わせを選ぶ』となります。数式に表せばxCyです。

組み合わせさえ出してしまえば全ての組み合わせを調べるだけなのであとはfor文でループさせより良い値がでたらその情報を持ってしまえばOKです。

最後に 

このような感じで実装はできましたが、なにせ総当たりなのでデータが多ければ実行には時間がかかります。なのでいつかはもう少し効率的なアルゴリズムでかいたものをアップできたらなと思います。