ARC-017-C 無駄なものが嫌いな人

■■■問題■■■

私は無駄なものが嫌いなので、無駄なことを言わずに言いたいことだけ言おう。
世の中にはナップサック問題というものがあり、決まった大きさのナップサックに
できるだけ価値が高くなるよう品物を詰めることを考えるらしいが、そんなことを考えても無駄である。

価値がいくら高くなったところで、
ナップサックに無駄なスペースができてしまうのは許せない。私は無駄なものが嫌いなのだ。
さて、今ここに大きさXのナップサックとN個の品物がある。

i番目の品物の大きさはwiである。品物の価値については、考えても無駄なので無視する。
ナップサックに無駄なスペースができないよう品物を詰める方法は何通りあるだろうか？

つまり、N個の品物から、
大きさの総和が無駄なくぴったりXとなる選び方が何通りあるか、ということだ。

私ははじめ手でこの問題を解こうとしたが、無駄が多い手段であると分かったので君に頼むことにした。
無駄な計算時間のないプログラムを書いてこの問題を解き、
私の無駄な時間を省くのを手伝ってもらいたい。 

■■■入力■■■

N X
w1
w2
・
・
・
wN

●1行目には、品物の個数を表す整数 N(1 <= N <= 32) と
  ナップサックの大きさを表す整数 X(1 <= X <= 10億) が半角空白区切りで与えられる。
●2行目からN行では、品物の大きさが与えられる。
  このうちi(1 <= i <= N) 行目には、
  i番目の品物の大きさを表す整数 wi(1 <= wi <= 5000万) が書かれている。

■■■出力■■■

N個の品物のうちいくつかを選び、
その大きさの和がぴったりXになるような方法が何通りあるかを表す整数を1行に出力せよ。 

C#のソース

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

class Program
{
    static string InputPattern = "InputX";

    static List GetInputList()
    {
        var WillReturn = new List();

        if (InputPattern == "Input1") {
            WillReturn.Add("5 5");
            WillReturn.Add("1");
            WillReturn.Add("1");
            WillReturn.Add("2");
            WillReturn.Add("3");
            WillReturn.Add("4");
            //4
            //無駄のない品物の選び方は次の4通りである。 
            //●品物1,品物2,品物4を選ぶ: 1+1+3=5
            //●品物1,品物5を選ぶ: 1+4=5
            //●品物2,品物5を選ぶ: 1+4=5
            //●品物3,品物4を選ぶ: 2+3=5
            //品物1と品物2は同じ重さの品物であるが
            //異なる品物として扱うことに注意すること。
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("8 21");
            WillReturn.Add("10");
            WillReturn.Add("4");
            WillReturn.Add("2");
            WillReturn.Add("30");
            WillReturn.Add("22");
            WillReturn.Add("20");
            WillReturn.Add("8");
            WillReturn.Add("14");
            //0
            //どのように品物を選んでも、
            //その大きさの和がぴったり21になるようにはできない。
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("20 100000000");
            WillReturn.Add("35576749");
            WillReturn.Add("38866484");
            WillReturn.Add("6624951");
            WillReturn.Add("39706038");
            WillReturn.Add("11133516");
            WillReturn.Add("25490903");
            WillReturn.Add("14701702");
            WillReturn.Add("17888322");
            WillReturn.Add("14423251");
            WillReturn.Add("32111678");
            WillReturn.Add("24509097");
            WillReturn.Add("43375049");
            WillReturn.Add("35298298");
            WillReturn.Add("21158709");
            WillReturn.Add("30489274");
            WillReturn.Add("37977301");
            WillReturn.Add("19510726");
            WillReturn.Add("28841291");
            WillReturn.Add("10293962");
            WillReturn.Add("12022699");
            //45
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("16 8");
            WillReturn.Add("1");
            WillReturn.Add("1");
            WillReturn.Add("1");
            WillReturn.Add("1");
            WillReturn.Add("1");
            WillReturn.Add("1");
            WillReturn.Add("1");
            WillReturn.Add("1");
            WillReturn.Add("1");
            WillReturn.Add("1");
            WillReturn.Add("1");
            WillReturn.Add("1");
            WillReturn.Add("1");
            WillReturn.Add("1");
            WillReturn.Add("1");
            WillReturn.Add("1");
            //12870
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        int[] wkArr = InputList[0].Split(' ').Select(A => int.Parse(A)).ToArray();
        int X = wkArr[1];

        int[] WArr = InputList.Skip(1).Select(A => int.Parse(A)).ToArray();
        int UB = WArr.GetUpperBound(0);

        //半分全探索で解く
        var ZenhanDict = PatternDict(WArr, 0, UB / 2);
        var KouhanDict = PatternDict(WArr, UB / 2 + 1, UB);

        long AnswerCnt = 0;
        foreach (var EachPair in ZenhanDict) {
            int TagetKey = X - EachPair.Key;
            if (KouhanDict.ContainsKey(TagetKey)) {
                //積の法則
                AnswerCnt += EachPair.Value * KouhanDict[TagetKey];
            }
        }
        Console.WriteLine(AnswerCnt);
    }

    //始点と終点を引数として、場合の数[重さ合計]なDictを返す
    static Dictionary<int, int> PatternDict(int[] pWArr, int pStaInd, int pEndInd)
    {
        //場合の数[重さ合計]なDP表
        var DPDict = new Dictionary<int, int>();
        DPDict[0] = 1;

        for (int I = pStaInd; I <= pEndInd; I++) {
            int[] KeysArr = DPDict.Keys.ToArray();
            //01ナップサック問題なので降順にソート
            Array.Sort(KeysArr, (A, B) => B.CompareTo(A));

            foreach (int EachKey in KeysArr) {
                int NewKey = EachKey + pWArr[I];
                if (DPDict.ContainsKey(NewKey))
                    DPDict[NewKey] += DPDict[EachKey];
                else
                    DPDict[NewKey] = DPDict[EachKey];
            }
        }
        return DPDict;
    }
}

解説

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