DPL_1_H: 巨大ナップザック問題

問題へのリンク

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("4 5");
            WillReturn.Add("4 2");
            WillReturn.Add("5 2");
            WillReturn.Add("2 1");
            WillReturn.Add("8 3");
            //13
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("2 20");
            WillReturn.Add("5 9");
            WillReturn.Add("4 10");
            //9
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

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

    struct ResultDef
    {
        internal long SumVal;
        internal long SumOmosa;
    }

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

        long[] wkArr = { };
        Action<string> SplitAct = pStr =>
            wkArr = pStr.Split(' ').Select(pX => long.Parse(pX)).ToArray();

        SplitAct(InputList[0]);
        long WeightLimit = wkArr[1];

        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            ItemInfoDef WillAdd;
            WillAdd.Value = wkArr[0];
            WillAdd.Weight = wkArr[1];
            mItemInfoList.Add(WillAdd);
        }

        int UB = mItemInfoList.Count - 1;
        int UBHalf = UB / 2;

        var ZenhanItemList = new List<ItemInfoDef>();
        var KouhanItemList = new List<ItemInfoDef>();

        for (int I = 0; I <= UBHalf; I++) {
            ZenhanItemList.Add(mItemInfoList[I]);
        }
        for (int I = UBHalf + 1; I <= UB; I++) {
            KouhanItemList.Add(mItemInfoList[I]);
        }

        int ZenhanCompleteBit = (1 << ZenhanItemList.Count);
        int KouhanCompleteBit = (1 << KouhanItemList.Count);

        var ZenhanResultList = new List<ResultDef>();
        var KouhanResultList = new List<ResultDef>();

        for (int I = 0; I <= ZenhanCompleteBit; I++) {
            long SumVal = 0;
            long SumOmosa = 0;
            for (int J = 0; J <= ZenhanItemList.Count - 1; J++) {
                if ((I & (1 << J)) > 0) {
                    SumVal += ZenhanItemList[J].Value;
                    SumOmosa += ZenhanItemList[J].Weight;
                    if (SumOmosa > WeightLimit) break;
                }
            }
            if (SumOmosa <= WeightLimit) {
                ResultDef WillAdd;
                WillAdd.SumVal = SumVal;
                WillAdd.SumOmosa = SumOmosa;
                ZenhanResultList.Add(WillAdd);
            }
        }

        for (int I = 0; I <= KouhanCompleteBit; I++) {
            long SumVal = 0;
            long SumOmosa = 0;
            for (int J = 0; J <= KouhanItemList.Count - 1; J++) {
                if ((I & (1 << J)) > 0) {
                    SumVal += KouhanItemList[J].Value;
                    SumOmosa += KouhanItemList[J].Weight;
                    if (SumOmosa > WeightLimit) break;
                }
            }
            if (SumOmosa <= WeightLimit) {
                ResultDef WillAdd;
                WillAdd.SumVal = SumVal;
                WillAdd.SumOmosa = SumOmosa;
                KouhanResultList.Add(WillAdd);
            }
        }

        // 重さの昇順にソート
        KouhanResultList.Sort((A, B) => A.SumOmosa.CompareTo(B.SumOmosa));

        // 価値合計の最大値[重さ合計]
        var RunMaxDict = new Dictionary<long, long>();

        long CurrMax = long.MinValue;
        foreach (ResultDef EachResult in KouhanResultList) {
            if (CurrMax < EachResult.SumVal) {
                RunMaxDict[EachResult.SumOmosa] = EachResult.SumVal;
                CurrMax = EachResult.SumVal;
            }
        }

        long[] KeysArr = RunMaxDict.Keys.ToArray();

        long ZenhanMax = ZenhanResultList.Max(X => X.SumVal);
        long KouhanMax = KouhanResultList.Max(X => X.SumVal);
        long MaxSumVal = Math.Max(ZenhanMax, KouhanMax);

        foreach (ResultDef EachZenhan in ZenhanResultList) {
            long RestWeight = WeightLimit - EachZenhan.SumOmosa;

            int ResultInd = ExecNibunhou_LowerOrEqual_Max(RestWeight, KeysArr);
            if (ResultInd > -1) {
                long wkSumVal = EachZenhan.SumVal + RunMaxDict[KeysArr[ResultInd]];
                MaxSumVal = Math.Max(MaxSumVal, wkSumVal);
            }
        }
        Console.WriteLine(MaxSumVal);
    }

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

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

        int L = 0;
        int R = pArr.GetUpperBound(0);

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

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

解説

半分全探索で解いてます。