ARC223-A Unusual-Constraint Knapsack

問題へのリンク

C#のソース

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

class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("3");
            WillReturn.Add("3 10");
            WillReturn.Add("1 2");
            WillReturn.Add("3 1");
            WillReturn.Add("9 3");
            WillReturn.Add("3 20");
            WillReturn.Add("1 2");
            WillReturn.Add("3 1");
            WillReturn.Add("9 3");
            WillReturn.Add("4 15");
            WillReturn.Add("1 1");
            WillReturn.Add("3 2");
            WillReturn.Add("5 3");
            WillReturn.Add("10 4");
            //5
            //6
            //7
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static long[] GetSplitArr(string pStr)
    {
        return (pStr == "" ? new string[0] : pStr.Split(' ')).Select(pX => long.Parse(pX)).ToArray();
    }

    struct ItemInfoDef
    {
        internal long Weight;
        internal long Value;
    }
    static List<ItemInfoDef> mItemInfoList = new List<ItemInfoDef>();
    static ItemInfoDef[] mItemInfoArr;

    static void Main()
    {
        List<string> InputList = GetInputList();

        long[] wkArr = { };
        Action<string> SplitAct = (pStr) => wkArr = GetSplitArr(pStr);

        int CurrInd = 1;
        while (true) {
            if (CurrInd > InputList.Count - 1) break;

            SplitAct(InputList[CurrInd]);
            long N = wkArr[0];
            long W = wkArr[1];

            mItemInfoList.Clear();
            for (int I = CurrInd + 1; I <= CurrInd + 1 + N - 1; I++) {
                SplitAct(InputList[I]);
                ItemInfoDef WillAdd;
                WillAdd.Weight = wkArr[0];
                WillAdd.Value = wkArr[1];
                mItemInfoList.Add(WillAdd);
            }
            mItemInfoArr = mItemInfoList.ToArray();
            long Answer = Solve(W);
            Console.WriteLine(Answer);

            CurrInd += (int)N + 1;
        }
    }

    static long Solve(long pWeight)
    {
        long RestWeight = pWeight;

        var WeightList = new List<long>();
        for (long I = 0; I <= mItemInfoArr.GetUpperBound(0); I++) {
            WeightList.Add(mItemInfoArr[I].Weight);
        }

        var AnswerList = new List<long>();
        AnswerList.Add(0);

        var Stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        WillPush.CurrInd = WeightList.Count - 1;
        WillPush.RestWeight = pWeight;
        WillPush.ScoreSum = 0;
        Stk.Push(WillPush);

        while (Stk.Count > 0) {
            JyoutaiDef Popped = Stk.Pop();

            // 取得可能な最大重さなアイテムを求める
            int ResultInd = ExecNibunhou_LowerOrEqual_Max(Popped.RestWeight, WeightList);
            if (ResultInd == -1) {
                continue;
            }
            ResultInd = Math.Min((int)Popped.CurrInd, ResultInd);

            // 取る場合
            WillPush.CurrInd = ResultInd - 1;
            WillPush.RestWeight = Popped.RestWeight - mItemInfoArr[ResultInd].Weight;
            WillPush.ScoreSum = Popped.ScoreSum + mItemInfoArr[ResultInd].Value;
            AnswerList.Add(WillPush.ScoreSum);

            if (WillPush.CurrInd >= 0) {
                Stk.Push(WillPush);
            }

            // 取らない場合は、残りを全部取る
            if (ResultInd >= 1) {
                long RangeSum = GetRangeSum(0, ResultInd - 1);
                AnswerList.Add(Popped.ScoreSum + RangeSum);
            }
        }
        return AnswerList.Max();
    }

    struct JyoutaiDef
    {
        internal long CurrInd;
        internal long RestWeight;
        internal long ScoreSum;
    }

    static long GetRangeSum(long pRangeSta, long pRangeEnd)
    {
        long RangeSum = 0;
        for (long I = pRangeSta; I <= pRangeEnd; I++) {
            RangeSum += mItemInfoArr[I].Value;
        }
        return RangeSum;
    }

    // 二分法で、Val以下で最大の値を持つ、添字を返す
    static int ExecNibunhou_LowerOrEqual_Max(long pVal, List<long> pList)
    {
        if (pList.Count == 0) return -1;

        // 最後の要素がVal以下の特殊ケース
        if (pVal >= pList.Last()) {
            return pList.Count - 1;
        }
        // 最初の要素がVal超えの特殊ケース
        if (pVal < pList[0]) {
            return -1;
        }

        int L = 0;
        int R = pList.Count - 1;

        while (L + 1 < R) {
            int Mid = (L + R) / 2;

            if (pList[Mid] <= pVal) {
                L = Mid;
            }
            else {
                R = Mid;
            }
        }
        return L;
    }
}

解説

重さの制約をふまえ、分かりやすく10進数で考えます。

重さ 1 10 100 1000 10000 100000
価値 3  1   4    1     5      9

{ナップサックの残り容量 , 荷物をどこまで見たか , 価値合計}
を状態に持ち、以下のDFSで解けます。

まだ、取ってない荷物の中で、重さが最大の荷物を、見つける。
この荷物を取るなら、DFSを続ける。
この荷物を取らないなら、残りの全部の荷物を取り、DFSを枝切り