ナップサック問題を解いてみた

こんばんわ。

業務で組み合わせ最適化を扱う業務があったので、 ナップサック問題を解いてみました。

といっても、数学得意じゃないですし、Wikipediaに書いてる内容もほとんどわかってないですが。。。 色々調べた結果、「lpsolve」を使えば実現出来そうでしたので、これを使いました。 ※DLLは、リンク先のlp_solve_5.5.2.0_dev_win64.zipから取得しました。 ※lpsolve55のDLL読み込み部分は、lp_solve_5.5.2.0_vb.net.zipから取得しました。

ナップサック問題については、ここの例題を拝借しました。

lpsolveに関しては、日本語の参考サイトがほぼないので（英語読めないし）、適当に実装してるところもありますが、 たぶん、例題のサイトと同じ解になったので、あってると思います。 以下ソースです。

Module Module1
    Private Structure OkasiInfo
        Dim name As String
        Dim price As Double
        Dim kcal As Double
    End Structure

    Public Sub Main()
        Dim okashilist = Module1.GetOkashiList()
        lpsolve55.Init(".")

        Dim kcal = okashilist.Select(Function(v) v.kcal).ToList
        kcal.Insert(0, 0)

        Dim price = okashilist.Select(Function(v) v.price).ToList
        price.Insert(0, 0)

        Dim lp = lpsolve55.make_lp(0, okashilist.Count)

        'カロリーが高くなるように
        lpsolve55.set_maxim(lp)
        lpsolve55.set_obj_fn(lp, kcal.ToArray)

        '合計金額は、300円以下に
        lpsolve55.add_constraint(lp, price.ToArray, lpsolve55.lpsolve_constr_types.LE, 300)

        '各おかしは、1度しか選択出来ないように
        For i = 1 To okashilist.Count
            Dim row(okashilist.Count) As Double
            row(i) = 1
            lpsolve55.add_constraint(lp, row, lpsolve55.lpsolve_constr_types.LE, 1)
        Next

        '整数のみになるように
        For i = 0 To okashilist.Count
            lpsolve55.set_int(lp, i, True)
        Next

        '算出結果
        lpsolve55.solve(lp)

        Dim col_cnt = lpsolve55.get_Ncolumns(lp)
        Dim col(col_cnt) As Double

        '算出結果を取得
        lpsolve55.get_variables(lp, col)

        Dim sum_kcal As Integer
        Dim sum_price As Integer
        Dim j As Integer = 0
        For Each wk In okashilist
            If col(j) > 0 Then
                Console.WriteLine(String.Format("{0} \{1} {2}本", wk.name, wk.price, col(j)))

                sum_kcal = sum_kcal + wk.kcal * col(j)
                sum_price = sum_price + wk.price * col(j)
            End If

            j += 1
        Next
        Console.WriteLine("カロリ" & ":" & sum_kcal)
        Console.WriteLine("金額" & ":" & sum_price)

        Console.ReadLine()
    End Sub

    Private Function GetOkashiList() As List(Of OkasiInfo)
        Dim okasiList As New List(Of OkasiInfo)
        okasiList.Add(New OkasiInfo With {.name = "ポッキー", .price = 168, .kcal = 496})
        okasiList.Add(New OkasiInfo With {.name = "うまい棒", .price = 10, .kcal = 45})
        okasiList.Add(New OkasiInfo With {.name = "じゃがりこ", .price = 145, .kcal = 325})
        okasiList.Add(New OkasiInfo With {.name = "ベビースターラーメン", .price = 60, .kcal = 347})
        okasiList.Add(New OkasiInfo With {.name = "チロルチョコ", .price = 10, .kcal = 61})
        okasiList.Add(New OkasiInfo With {.name = "かっぱえびせん", .price = 124, .kcal = 486})
        okasiList.Add(New OkasiInfo With {.name = "サッポロポテト", .price = 124, .kcal = 446})
        okasiList.Add(New OkasiInfo With {.name = "都こんぶ", .price = 105, .kcal = 22})
        okasiList.Add(New OkasiInfo With {.name = "ヨーグレッとは入れもん", .price = 126, .kcal = 110})
        okasiList.Add(New OkasiInfo With {.name = "おにぎりせんべい", .price = 184, .kcal = 475})

        Return okasiList

    End Function
End Module