【C#】ナップザック問題を解いてみる

はじめに

今回はナップザック問題を解いてみようという記事になります。
ja.wikipedia.org

ナップザック問題は動的計画法の典型例なので、アルゴリズムの勉強にも良い問題だと思います。

早速みていきましょう。

はじめに
ナップザック問題とは
問題
方針
実装
使い方
さいごに

ナップザック問題とは

「容量 C のナップサックが一つと、n 種類の品物（各々、価値 pi, 容積 ci）が与えられたとき、ナップサックの容量 C を超えない範囲でいくつかの品物をナップサックに詰め、ナップサックに入れた品物の価値の和を最大化するにはどの品物を選べばよいか」

ナップサック問題 - Wikipedia

$I = {1,2,...,N}$ を品物の集合とし，各品目 $i \in I$ の重みを $w_i$ , 価値を $v_i$ ,品物の最大容量を $W$ としたとき，以下のように数式でかけます。

$\max\sum_{i \in I}v_ix_i$
$s.t.\sum_{i \in I}w_ix_i \leq W　, x_i \in \bf N$

$x_i$ はナップサックへ入れる品物の個数を指します。

問題

今回は $x_i \in {0, 1}$ ，つまり選ぶ・選ばないだけの0/1ナップサック問題を解いてみます。
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_B&lang=jp

方針

まずは実装の方針を簡単化するために荷物(品物)の数Nを4こ，ナップザックの容量Wを5とし，各荷物(品物)の価値v・重さ(容量)wを以下のように考えます。

(価値v, 重さｗ) = (4, 2), (5, 2), (2, 1), (8, 3)

今回の記事は実装が目的なので細かい詳細は省きますが、ざっくりとまとめるとN+1 * W+1の表を埋めることで答えを導きます。

詳細は以下の記事にめちゃくちゃ丁寧に書かれているので、こちらを一読ください。
典型的な DP (動的計画法) のパターンを整理 Part 1 ～ナップサック DP 編～ - Qiita

dp[i+1][w] := i 番目までの品物の中から重さが w を超えないように選んだときの、価値の総和の最大値

この定義を踏まえながら、以下の手法で表を埋めていきます。
f:id:hanaaaaaachiru:20200601194339p:plain

f:id:hanaaaaaachiru:20200601222106p:plain

実装

public class KnapsackProblem
{
    private Item[] _items;

    public KnapsackProblem(IEnumerable<Item> items)
    {
        _items = items.ToArray();
    }

    public int[][] Solve(int W)
    {
        int N = _items.Length;

        var dp = new int[N + 1][].Select(t => t = new int[W+1]).ToArray();

        // DP初期条件
        for (int j = 0; j < W; j++) dp[0][j] = 0;

        // DPループ
        for (int i = 0; i < N; i++)
        {
            for (int w = 0; w <= W; w++)
            {
                if (w >= _items[i].Weight) dp[i + 1][w] = Math.Max(dp[i][w - _items[i].Weight] + _items[i].Value, dp[i][w]);
                else dp[i + 1][w] = dp[i][w];
            }
        }

        return dp;
    }
}

使い方

class Program
{
    static void Main(string[] args)
    {
        var NW = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
        var N = NW[0];
        var W = NW[1];
        var items = new Item[N];

        for (int i = 0; i < N; i++)
        {
            var item = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
            items[i] = new Item(item[0], item[1]);
        }

        var problem = new KnapsackProblem(items);
        var dp = problem.Solve(W);

        Console.WriteLine(dp.Last().Last());
    }
}