No.4 おもりと天秤

■■■問題■■■

授業中にもかかわらず遊んでしまうdaveは、
理科の実験中に、色んな重さの種類があるおもりをすべて使って、
ちょうど天秤が水平になるおもりの組み合わせがあるかを知りたくなったようで、それに遊び呆けてる。
(すべてのおもりを使うため、使わなかったおもりはないとする)

あなたは、daveにその組み合わせがあるかどうか教えて、授業に集中させるようにしてください。
もしそのような組み合わせがあればpossible、なければimpossibleを出力してください。

■■■入力■■■

N
W1 W2 W3　・・・ WN
1行目におもりの数を表す N (2 <= N <= 100) が与えられます。
2行目にそれぞれのおもりの重さを表す Wi (1 <= Wi <= 100) がスペース区切りで与えられます。
WiとWjは、同じ値がある場合もあります。

■■■出力■■■

possibleまたはimpossibleを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("3");
            WillReturn.Add("1 2 3");
            //possible
            //左側に1と2 右側に3を置くことで水平になります。
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("5");
            WillReturn.Add("1 2 3 4 5");
            //impossible
            //すべてのおもりを使って水平になる組み合わせは存在しません
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("15");
            WillReturn.Add("62 8 90 2 24 62 38 64 76 60 30 76 80 74 72");
            //impossible
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

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

        //事前に総合計を求めておく
        int OmoriSum = OmoriArr.Sum();

        //総合計が奇数なら解なし
        if (OmoriSum % 2 == 1) {
            Console.WriteLine("impossible");
            return;
        }

        //作成可否[重りの合計]なDP表
        bool[] DPArr = new bool[OmoriSum / 2 + 1];
        DPArr[0] = true;

        foreach (int EachOmosa in OmoriArr) {
            //01ナップサックなのでリバースループ
            for (int I = DPArr.GetUpperBound(0); 0 <= I; I--) {
                if (DPArr[I] == false) continue;
                int wkInd = I + EachOmosa;
                if (wkInd <= DPArr.GetUpperBound(0))
                    DPArr[wkInd] = true;
            }
        }
        Console.WriteLine(DPArr[OmoriSum / 2] ? "possible" : "impossible");
    }
}

解説

動的計画法で、作成可能な重りの合計をメモしていって、
最後に、総合計/2を作れるかを判定してます。