8-1 ナップサック問題

問題

ALGORITHM NOTE ナップザック問題 Knapsack Problem
最強最速アルゴリズマー養成講座 --- 病みつきになる「動的計画法」、その深淵に迫る (1/4)

5つの荷物(重量と価値はそれぞれ、(3と2) (4と3) (1と2) (2と3) (3と6) が各1個)がある。
重量の合計が10以下で、最も価値の合計が高くなるような荷物の組合せを見つけよ。

荷物名  重量  価値
------  ----  ----
A       3      2
B       4      3
C       1      2
D       2      3
E       3      6

ソース(深さ優先探索)

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    struct ItemInfoDef
    {
        internal char ID;
        internal int Omosa;
        internal int Val;
    }

    static List<ItemInfoDef> ItemList = new List<ItemInfoDef>();

    struct JyoutaiDef
    {
        internal int CurrP;
        internal int OmosaSum;
        internal int SumVal;
        internal List<ItemInfoDef> SelectedItemList;
    }

    //重さ合計の制限
    const int OmosaSumLimit = 10;

    static void Main()
    {
        ItemList.Add(new ItemInfoDef() { ID = 'A', Omosa = 3, Val = 2 });
        ItemList.Add(new ItemInfoDef() { ID = 'B', Omosa = 4, Val = 3 });
        ItemList.Add(new ItemInfoDef() { ID = 'C', Omosa = 1, Val = 2 });
        ItemList.Add(new ItemInfoDef() { ID = 'D', Omosa = 2, Val = 3 });
        ItemList.Add(new ItemInfoDef() { ID = 'E', Omosa = 3, Val = 6 });

        var JyoutaiDefList = new List<JyoutaiDef>();
        var stk = new Stack<JyoutaiDef>();
        for (int I = 0; I <= ItemList.Count - 1; I++) {
            JyoutaiDef WillPush;
            WillPush.CurrP = I;
            WillPush.OmosaSum = ItemList[I].Omosa;
            WillPush.SumVal = ItemList[I].Val;
            WillPush.SelectedItemList = new List<ItemInfoDef>() { ItemList[I] };
            stk.Push(WillPush);
        }

        while (stk.Count > 0) {
            JyoutaiDef Popped = stk.Pop();
            JyoutaiDefList.Add(Popped);

            for (int I = Popped.CurrP + 1; I <= ItemList.Count - 1; I++) {
                JyoutaiDef WillPush;
                WillPush.CurrP = I;
                WillPush.OmosaSum = Popped.OmosaSum + ItemList[I].Omosa;
                WillPush.SumVal = Popped.SumVal + ItemList[I].Val;
                WillPush.SelectedItemList = new List<ItemInfoDef>(Popped.SelectedItemList);
                WillPush.SelectedItemList.Add(ItemList[I]);

                if (WillPush.OmosaSum <= OmosaSumLimit) stk.Push(WillPush);
            }
        }

        int MaxSumVal = JyoutaiDefList.Max(X => X.SumVal);
        JyoutaiDef AnswerJyoutai = JyoutaiDefList.First(X => X.SumVal == MaxSumVal);

        Console.WriteLine("深さ優先探索の結果を表示します。");
        Console.WriteLine("重さ合計が{0}以下での最大の価値は、", OmosaSumLimit);
        Console.WriteLine("重さ合計={0}で価値合計={1}です。", AnswerJyoutai.OmosaSum, MaxSumVal);
        Console.WriteLine();
        Console.WriteLine(new string('■', 30));
        Console.WriteLine("選択した荷物の情報を表示します。");

        foreach (ItemInfoDef EachItem in AnswerJyoutai.SelectedItemList) {
            Console.WriteLine("ID={0}、重さ={1}、価値={2}",
                EachItem.ID, EachItem.Omosa, EachItem.Val);
        }
    }
}

実行結果(深さ優先探索)

重さ合計が10以下での最大の価値は、
重さ合計=10で価値合計=14です。

■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■
選択した荷物の情報を表示します。
ID=B、重さ=4、価値=3
ID=C、重さ=1、価値=2
ID=D、重さ=2、価値=3
ID=E、重さ=3、価値=6

ソース(動的計画法)

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    struct ItemInfoDef
    {
        internal char ID;
        internal int Omosa;
        internal int Val;
    }

    static List<ItemInfoDef> ItemList = new List<ItemInfoDef>();

    //重さ合計の制限
    const int OmosaSumLimit = 10;

    //価値合計の最大値[重さの合計]のDP表
    static Nullable<int>[] DPArr = new Nullable<int>[OmosaSumLimit + 1];

    //最後に矢印をセットした品物の名称
    static char[] LastArrowItemArr = Enumerable.Repeat(' ', OmosaSumLimit + 1).ToArray();
    static List<char[]> LastArrowItemArrLog = new List<char[]>();

    static void Main()
    {
        ItemList.Add(new ItemInfoDef() { ID = 'A', Omosa = 3, Val = 2 });
        ItemList.Add(new ItemInfoDef() { ID = 'B', Omosa = 4, Val = 3 });
        ItemList.Add(new ItemInfoDef() { ID = 'C', Omosa = 1, Val = 2 });
        ItemList.Add(new ItemInfoDef() { ID = 'D', Omosa = 2, Val = 3 });
        ItemList.Add(new ItemInfoDef() { ID = 'E', Omosa = 3, Val = 6 });

        //初期設定
        DPArr[0] = 0;

        foreach (ItemInfoDef EachItem in ItemList) {
            for (int I = OmosaSumLimit; 0 <= I; I--) {
                //重さ制限を超えてしまう場合
                int wkSumOmosa = I + EachItem.Omosa;
                if (wkSumOmosa > OmosaSumLimit) continue;

                //価値の和を求める
                if (DPArr[I] == null) continue;
                int wkSumVal = DPArr[I].Value + EachItem.Val;

                //重さ合計での最大の価値を更新可能かを判定
                if (DPArr[wkSumOmosa] == null
                 || DPArr[wkSumOmosa] < wkSumVal) {
                    DPArr[wkSumOmosa] = wkSumVal;
                    LastArrowItemArr[wkSumOmosa] = EachItem.ID;
                }
            }
            LastArrowItemArrLog.Add((char[])LastArrowItemArr.Clone());
            Console.WriteLine(new string('■', 30));
            Console.WriteLine("{0}の処理結果", EachItem.ID);
            PrintJyoutai();
        }
        Console.WriteLine(new string('■', 30));
        Console.WriteLine("動的計画法の結果を表示します。");
        PrintDP();
    }

    //動的計画法の現在の状態を表示
    static void PrintJyoutai()
    {
        var sb1 = new System.Text.StringBuilder();
        var sb2 = new System.Text.StringBuilder();

        for (int I = 0; I <= DPArr.GetUpperBound(0); I++) {
            sb1.AppendFormat("[{0,2}]", I);
            sb2.AppendFormat(" {0,2} ", DPArr[I]);
        }

        Console.WriteLine(sb1.ToString());
        Console.WriteLine(sb2.ToString());
        Console.WriteLine();

        sb1.Length = sb2.Length = 0;

        for (int I = 0; I <= LastArrowItemArr.GetUpperBound(0); I++) {
            sb1.AppendFormat("[{0,2}]", I);
            sb2.AppendFormat(" {0,2} ", LastArrowItemArr[I]);
        }
        Console.WriteLine(sb1.ToString());
        Console.WriteLine(sb2.ToString());
    }

    //動的計画法の結果を表示
    static void PrintDP()
    {
        //最大の価値を持つ、重さ合計を求める
        int MaxSumVal = DPArr.Max(X => X ?? 0);
        int MaxSumInd = Array.FindIndex(DPArr, X => X == MaxSumVal);

        Console.WriteLine("重さ合計が{0}以下での最大の価値は、", OmosaSumLimit);
        Console.WriteLine("重さ合計={0}で価値合計={1}です。", MaxSumInd, MaxSumVal);
        Console.WriteLine();
        Console.WriteLine(new string('■', 30));

        Console.WriteLine("選択した荷物の情報を表示します。");

        int CurrInd = MaxSumInd;
        var SelectedItemList = new List<ItemInfoDef>();

        for (int I = LastArrowItemArrLog.Count - 1; 0 <= I; I--) {
            char[] CurrLog = LastArrowItemArrLog[I];

            //使用済の荷物を含むログならContinue
            if (CurrLog.Intersect(SelectedItemList.Select(X => X.ID)).Any()) {
                continue;
            }

            ItemInfoDef CurrArrowItem = ItemList.Single(X => X.ID == CurrLog[CurrInd]);
            SelectedItemList.Add(CurrArrowItem);
            CurrInd -= CurrArrowItem.Omosa;

            if (CurrInd == 0) break;
        }

        foreach (ItemInfoDef EachItem in SelectedItemList) {
            Console.WriteLine("ID={0}、重さ={1}、価値={2}",
                EachItem.ID, EachItem.Omosa, EachItem.Val);
        }
    }
}

実行結果(動的計画法)

■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■
Aの処理結果
[ 0][ 1][ 2][ 3][ 4][ 5][ 6][ 7][ 8][ 9][10]
  0           2

[ 0][ 1][ 2][ 3][ 4][ 5][ 6][ 7][ 8][ 9][10]
              A
■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■
Bの処理結果
[ 0][ 1][ 2][ 3][ 4][ 5][ 6][ 7][ 8][ 9][10]
  0           2   3           5

[ 0][ 1][ 2][ 3][ 4][ 5][ 6][ 7][ 8][ 9][10]
              A   B           B
■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■
Cの処理結果
[ 0][ 1][ 2][ 3][ 4][ 5][ 6][ 7][ 8][ 9][10]
  0   2       2   4   5       5   7

[ 0][ 1][ 2][ 3][ 4][ 5][ 6][ 7][ 8][ 9][10]
      C       A   C   C       B   C
■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■
Dの処理結果
[ 0][ 1][ 2][ 3][ 4][ 5][ 6][ 7][ 8][ 9][10]
  0   2   3   5   4   5   7   8   7   8  10

[ 0][ 1][ 2][ 3][ 4][ 5][ 6][ 7][ 8][ 9][10]
      C   D   D   C   C   D   D   C   D   D
■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■
Eの処理結果
[ 0][ 1][ 2][ 3][ 4][ 5][ 6][ 7][ 8][ 9][10]
  0   2   3   6   8   9  11  10  11  13  14

[ 0][ 1][ 2][ 3][ 4][ 5][ 6][ 7][ 8][ 9][10]
      C   D   E   E   E   E   E   E   E   E
■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■
動的計画法の結果を表示します。
重さ合計が10以下での最大の価値は、
重さ合計=10で価値合計=14です。

■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■
選択した荷物の情報を表示します。
ID=E、重さ=3、価値=6
ID=D、重さ=2、価値=3
ID=C、重さ=1、価値=2
ID=B、重さ=4、価値=3

解説

深さ優先探索よりも、動的計画法で解いたほうが、計算量は、少ないです。