ABC-060-D Simple Knapsack

■■■問題■■■

あなたはN個の物と、強度Wのバッグを持っています。
i個目の物は、重さがwiで価値がviです。

あなたは、物のうちいくつかを選び、バッグに入れます。
ただし、選んだ物の重さの和はW以下でなくてはいけません。

あなたは、バッグに入れた物の価値の総和を最大化したいです。

■■■入力■■■

N W
w1 v1
w2 v2
・
・
・
wN vN

●1 <= N <= 100
●1 <= W <= 10億
●1 <= wi <= 10億
●すべての i=2,3, ・・・ ,N について、w1 <= wi <= w1+3
●1 <= vi <= 1000万
●W,wi,vi はすべて整数である

■■■出力■■■

価値の総和の最大値を出力する。

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("4 6");
            WillReturn.Add("2 1");
            WillReturn.Add("3 4");
            WillReturn.Add("4 10");
            WillReturn.Add("3 4");
            //11
            //1,3個目の物を選ぶと良いです
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("4 6");
            WillReturn.Add("2 1");
            WillReturn.Add("3 7");
            WillReturn.Add("4 10");
            WillReturn.Add("3 6");
            //13
            //2,4個目の物を選ぶと良いです
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("4 10");
            WillReturn.Add("1 100");
            WillReturn.Add("1 100");
            WillReturn.Add("1 100");
            WillReturn.Add("1 100");
            //400
            //すべての物が選べます
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("4 1");
            WillReturn.Add("10 100");
            WillReturn.Add("10 100");
            WillReturn.Add("10 100");
            WillReturn.Add("10 100");
            //0
            //1個も物が選べません
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    struct NimotuDef
    {
        internal int W;
        internal int V;
    }

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

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

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

        var NimotuList = new List<NimotuDef>();
        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            NimotuList.Add(new NimotuDef() { W = wkArr[0], V = wkArr[1] });
        }

        //最大の価値[重さ合計]なDP表
        var DPDict = new Dictionary<int, int>();
        DPDict[0] = 0;

        foreach (NimotuDef EachNimotu in NimotuList) {
            foreach (int EachKey in DPDict.Keys.OrderByDescending(A => A).ToArray()) {
                int NewKey = EachKey + EachNimotu.W;
                if (NewKey > W) continue;

                int NewVal = DPDict[EachKey] + EachNimotu.V;

                if (DPDict.ContainsKey(NewKey)) {
                    if (DPDict[NewKey] < NewVal) {
                        DPDict[NewKey] = NewVal;
                    }
                }
                else DPDict[NewKey] = NewVal;
            }
        }
        Console.WriteLine(DPDict.Values.Max());
    }
}

解説

重さの範囲が狭いので、最大の価値合計[重さ合計]でDPしてます。