ABC-015-D 高橋くんの苦悩

■■■問題■■■

高橋くんは、ソフトウエアが期待通りに動いたというエビデンス（証拠）として、
画面のスクリーンショットを表計算ソフトに貼り付ける作業を命じられました。

画面のスクリーンショットはN枚あり、高さは全て等しいのですが、幅が異なります。
また、表計算ソフトに貼りつけ可能なスクリーンショットには2つの制約が存在します。

1.表計算ソフトの幅はWしかない。
  そのため、貼りつけるスクリーンショットの幅の合計値はW以下でなければならない。
  
2.表計算ソフトはK枚より多くのスクリーンショットを貼りつけることが出来ない。
  よって、表計算ソフトに貼りつけ可能なスクリーンショットはK枚までである。

さらに、スクリーンショットには「重要度」が存在するため、
高橋くんは2つの制約を満たしながら、
貼り付けるスクリーンショットが持つ重要度の合計値を最大化したいです。

しかし、彼にとってこの仕事は難しいので、あなたが彼の代わりに
表計算ソフトに貼り付け可能なスクリーンショットが持つ重要度の合計の最大値を求めてください。

■■■入力■■■

W
N K
A1 B1
A2 B2
・
・
・
AN BN

●1行目には、表計算ソフトの幅 W(1 <= W <= 1万) が与えられる。
●2行目には、スクリーンショットの数 N(1 <= N <= 50) と、
  表計算ソフトに貼り付け可能なスクリーンショットの枚数 K(1 <= K <= N) が、
  スペース区切りで与えられる。
●3行目からN行では、各スクリーンショットに関する情報が与えられる。
  このうち i 行目では i 番目のスクリーンショットにおける、
  幅 Ai(1 <= Ai <= 1000) と、重要度 Bi(1 <= Bi <= 100) の値が、
  スペース区切りで与えられる。

■■■出力■■■

表計算ソフトに貼り付け可能なスクリーンショットが持つ重要度の合計の最大値を1行で出力せよ。
出力の末尾には改行をいれること。

C#のソース

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

class Program
{
    static string InputPattern = "Input1";

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

        if (InputPattern == "Input1") {
            WillReturn.Add("10");
            WillReturn.Add("3 2");
            WillReturn.Add("4 20");
            WillReturn.Add("3 40");
            WillReturn.Add("6 100");
            //140
            //2番目と3番目のスクリーンショットを選ぶと、
            //合計の幅が 9 、使用するスクリーンショットが2枚となり、条件を満たす。
            //この時の重要度の和は、40+100で140となる。
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("10");
            WillReturn.Add("5 4");
            WillReturn.Add("9 10");
            WillReturn.Add("3 7");
            WillReturn.Add("3 1");
            WillReturn.Add("2 6");
            WillReturn.Add("4 5");
            //18
            //必ずK枚のスクリーンショットを使わなくても良いことに注意してください
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("22");
            WillReturn.Add("5 3");
            WillReturn.Add("5 40");
            WillReturn.Add("8 50");
            WillReturn.Add("3 60");
            WillReturn.Add("4 70");
            WillReturn.Add("6 80");
            //210
            //幅が足りていても、
            //スクリーンショットを最大でK枚までしか置けないことに注意してください。
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    struct PairDef
    {
        internal int A;
        internal int B;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        int W = int.Parse(InputList[0]);

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

        SplitAct(InputList[1]);
        int N = wkArr[0];
        int K = wkArr[1];

        PairDef[] PairArr = new PairDef[N];
        for (int I = 0; I <= PairArr.GetUpperBound(0); I++) {
            SplitAct(InputList[I + 2]);
            PairArr[I].A = wkArr[0];
            PairArr[I].B = wkArr[1];
        }

        //重要度の合計[幅合計,枚数合計]なDP表
        var DPArr = new Nullable<int>[W + 1, K + 1];
        DPArr[0, 0] = 0;

        int MaxVal = 0;
        foreach (PairDef EachPairInfo in PairArr) {
            for (int LoopA = W; 0 <= LoopA; LoopA--) {
                int NewA = LoopA + EachPairInfo.A;
                if (W < NewA) continue;
                for (int LoopK = K; 0 <= LoopK; LoopK--) {
                    int NewK = LoopK + 1;
                    if (K < NewK) continue;

                    if (DPArr[LoopA, LoopK].HasValue == false) continue;
                    int NewVal = DPArr[LoopA, LoopK].Value + EachPairInfo.B;

                    if (DPArr[NewA, NewK] == null || DPArr[NewA, NewK] < NewVal) {
                        DPArr[NewA, NewK] = NewVal;
                        if (MaxVal < NewVal)
                            MaxVal = NewVal;
                    }
                }
            }
        }
        Console.WriteLine(MaxVal);
    }
}

解説

動的計画法で解いてます。