puthon のナップザック問題で値が変わる

Question

7トン、4トン、5トン、6トン、3トンの５種類の荷物があり、制限質量１５トンに収めるというナップザック問題を解いています。以下のようにコードを書いたのですが、１５トンぴったりの組み合わせが表示されません。符号が間違っているのでしょうか。教えていただけたら嬉しいです。よろしくお願いいたします。

class Item:
    def __init__(self,name,weight):#クラスの定義
        self.name=name
        self.weight=weight
        


#初期化する
limit = 15
items=[Item("A",7),Item("B",4),Item("C",5),Item("D",6),Item("E",3)]
L=len(items)


result=[]#結果を入れる

def judge(i,select):
    
    if select+items[i].weight<limit:
        select +=items[i].weight
        result.append(items[i].name)
        if i<L-1:
            judge(i+1,select)
    if select+items[i].weight>limit:
        select+=0
        if i<L-1:
            judge(i+1,select)
    
            

select=0
judge(0,0)

print('選んだ荷物の組み合わせは')
print(result)

Answer 1

前から選んで、入れることができたら受け入れるという特に探索をしていないコードだからではないですか？

総当たり：
https://wandbox.org/permlink/8ug63FVQMO8Ef815

class Item:
    def __init__(self,name,weight):#クラスの定義
        self.name=name
        self.weight=weight

#初期化する
limit = 15
items=[Item("A",7),Item("B",4),Item("C",5),Item("D",6),Item("E",3)]
L=len(items)

import itertools

def calc_total_weight(items, choices, limit=15):
    ret = sum([x.weight*a for x, a in zip(items, choices)])
    if ret > limit:
        return 0
    return ret

choices_weight = [(choices, calc_total_weight(items, choices, limit=limit))
                  for choices in itertools.product([0, 1], repeat=L)]
ans = list(sorted(choices_weight, key=lambda x: x[1], reverse=True))

print('選んだ荷物の組み合わせの重みは')
print(ans[0][1])
best_weight = ans[0][1]
for v in ans:
    if v[1] < best_weight:
        break
    print('選んだ荷物の組み合わせは')
    print(v[0])
    print([items[i].name for i, v in enumerate(v[0]) if v == 1])

Answer 2

ナップザック問題ですと組み合わせ最適化のナップザック問題ですかね？
最適化の考えですとA B C D Eのナップザック(集合Ai)には利用価値Ciが付与されており
それぞれの重さがXiとします。この場合重さの集合は
Wを１５トンとします
Xi=(X1 X2 X3 X4 X5)=(7 4 5 6 3)ですので

目的関数: ΣCiAi=C1A1+C2A2+C3A3+C4A4+C5A5→Max
制約条件: ΣXiAi=7A1+4A2+5A3+6A4+3A5=<W=15

と定式化できますが
ここで優先指標を決めます。
ΣXi/Ciとします
優先指標は
この条件（今回は各重さに対して利用価値の割合が大きいものを優先してナップザックに詰めるというものです）に満たすか
条件に対しては貪欲法を用いてA B C D E で見ていくとしましょう。

となるわけです。
とりあえず価値Ciなしでは解を求められないのではないかと思います。
今の段階だと単純に品物集合から足して15になる重さの組み合わせしか求められないきがします。
コードを詳しく見たわけではありませんので何かほかの価値総和があれば教えてください。

Comments

[h_proc]

回答ありがとうございます。品物番号と質量以外に価値は設定されていません。正しければ１、正しくなければ０といった価値判断でもいいのでしょうか。

[flan]

はい、いいと思います。
https://qiita.com/drken/items/a5e6fe22863b7992efdb
↑このサイトの一問目に同じような問題がありました。
大学では価値総和があるものしか教わらなかったたので・・・。
動的計画法の制約なし最適化のほうでナップザック問題があるのですね。
失礼しました・・・

前提として重さを最大にしたい。この場合は15にしたいということで
Ｂ　Ｃ　Ｄあたりが選ばれるとうれしいということでしょうか。

肝心のコードですが
result.append(items[i].name)
↑
ここでおそらく強制的にＡが選ばれてしまうためおかしくなるのではないかなと思いました。
あまり自信はありません・・・

[flan]

はい、いいと思います。
https://qiita.com/drken/items/a5e6fe22863b7992efdb
↑このサイトの一問目に同じような問題がありました。
大学では価値総和があるものしか教わらなかったたので・・・。
動的計画法の制約なし最適化のほうでナップザック問題があるのですね。
失礼しました・・・

前提として重さを最大にしたい。この場合は15にしたいということで
Ｂ　Ｃ　Ｄあたりが選ばれるとうれしいということでしょうか。

肝心のコードですが
result.append(items[i].name)
↑
ここでおそらく強制的にＡが選ばれてしまうためおかしくなるのではないかなと思いました。
あまり自信はありません・・・

あ、あとこれはＡから決めて始めているので
次はＢ
次はＣ
・・・・
といったようにfor分で回すといいです。
そしてそのfor分の中で例えばBを最初に選んだ場合
C D Eと行くのがワンクール
次は
DEというのがワンクールと
全て見れるようにして
一番大きい組み合わせを配列に持つといいです。
こうすることで取りこぼしがなく見つけられますね
つまり
for i in 集合Ai
for j in 集合Ai
judge
でいいとおもいます。