はじめに

「会社で業務の傍ら採用のお手伝いをしているけど、あんまり募集進んでない・・・いいアピールの方法ないかな？」
と思っていたところ、日頃お世話になっているQiitaで面白そうなキャンペーンを見つけて、

「これ使えないかな？」
と試験的に投稿してみることにしました。所属企業を公開されてる方たちもいるしね。
~~決してApple Watchがほしいわけではありません。うん。~~

問題を見てみて、「ハノイの塔がAかー、このくらいのランクならなんとか解けそうかな？」
ということで、チャレンジしてみました。言語はC#です。
それではどうぞ。

お菓子の詰め合わせ（初回提出)

考え方

条件は以下3つ。
・商品は種類ごとに1つしか買うことはできない
・与えられた金額でできるだけ多くの商品を買うこと
・商品の個数が同じであれば、できるだけおつりが少なくなるように買うこと

解法は以下のように考えた。

商品を安い順から買えるだけ買う ( = できるだけ多くの商品を買うことが可能)
買った商品とそれ以外のより高い商品を比較し、差額が予算内に納まれば商品を交換する( = できるだけ高い商品を買い、おつりを少なくする）

ソースコード

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

class Program
{
    static void Main()
    {
        // 1行目(種類, 総額)の取得
        var line1 = Console.ReadLine().Split(' ');
        var kind = int.Parse(line1[0]);
        var amount = int.Parse(line1[1]);
        
        // 2行目以降(商品)の取得
        var products = new List<int>();
        for (int ii = 0; ii < kind; ++ii)
        {
            products.Add(int.Parse(Console.ReadLine()));
        }
        
        // 昇順ソート必須
        products.Sort();
        
        //最少額の商品から限界まで購入する(購入可能な種類数を求める) 
        var boughtList = new List<int>();
        foreach (var product in products)
        {
            if ((boughtList.Sum() + product) > amount) { break; }
            boughtList.Add(product);
        }

        // 購入した商品から、残金の範囲でできるだけ高い金額の商品と交換する
        for (int ii = 0; ii < boughtList.Count; ++ii)
        {
            var preOrder = -1;
            foreach (var product in products)
            {
                // すでに購入していた商品は除く
                if (boughtList.Contains(product)) { continue; }
                // 購入した商品より高額、かつ総額の範囲に納まる商品を探す
                if ( (product > boughtList[ii]) &&
                     (boughtList.Sum() + (product - boughtList[ii]) <= amount) )
                {
                    // 交換可能な商品を仮押さえしておき、差額の大きい商品があれば更新する
                    preOrder = product;
                }
            }
            // できるだけ差額の大きい商品と交換する
            if (preOrder >= 0) { boughtList[ii] = preOrder; }
        }
        
        // 購入した商品の残額を出力する
        Console.WriteLine(amount - boughtList.Sum());
    }
}

結果（初回提出)

foreachしてるコレクションをループ中に変更するなんてダメだろ、とコンパイラ様にマサカリを投げられる恐怖を抱えつつ、まあ通ったしええやろの精神で提出。
~~赤点の予感を感じつつテストを提出した気分でした。~~

結果は・・・

思ったよりいい。
1パターン通らなかったらしく、しっくりこないので確認する

気づき

「これ結局、総当たり必要じゃね？」
そう、最もお釣りの少なくなる組み合わせが欲しいのであって、それは必ずしも高い商品ではないのだ。（とても高い商品と安い商品のパターンもあれば、すべてそこそこ高い商品のパターンもある）
ひとつずつ交換していたのでは正しい答えは得られない。

「いい考えだと思ったのになぁ」とうなだれつつ、コードを修正する。~~まるで現実のようだ~~

最終提出

解法1. の「商品を安い順から買えるだけ買う」の部分に関しては正しいはずなので、商品の個数は求められた前提でコードを修正した。

ソースコード

using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
    static void Main()
    {
        // 1行目(種類, 総額)の取得
        var line1 = Console.ReadLine().Split(' ');
        var kind = int.Parse(line1[0]);
        var amount = int.Parse(line1[1]);

        // 2行目以降(商品)の取得
        var products = new List<int>();
        for (int ii = 0; ii < kind; ++ii)
        {
            products.Add(int.Parse(Console.ReadLine()));
        }

        // 昇順ソート必須
        products.Sort();

        //最少額の商品から限界まで購入する(購入可能な種類数を求める) 
        var boughtList = new List<int>();
        foreach (var product in products)
        {
            if ((boughtList.Sum() + product) > amount) { break; }
            boughtList.Add(product);
        }

        // 修正部分
        var productCount = boughtList.Count;
        boughtList.Clear();

        var sum = ChoiseProducts(products, productCount, amount);

        // 購入した商品の残額を出力する
        Console.WriteLine(amount - sum);
    }

    // 再帰関数を追加
    public static int ChoiseProducts(List<int> productList, int productCount, int amount, int oldSum = 0, int sum = 0)
    {
        --productCount;

        foreach (var product in productList)
        {
            // 商品を買う
            sum += product;

            // 最大個数の商品を買うまで繰り返す
            if (productCount > 0)
            {
                // 購入した商品を除いて他の商品をチョイスする
                var copyProductList = new List<int>(productList);
                copyProductList.Remove(product);
                oldSum = ChoiseProducts(copyProductList, productCount, amount, oldSum, sum);
            }

            // よりお釣りの少ない組み合わせが見つかったら合計を更新する
            if ((productCount == 0) && (sum <= amount) && (sum > oldSum))
            {
                oldSum = sum;
            }
            sum -= product;
        }

        return oldSum;
    }
}

なんか、コレジャナイ感。。。
うまぶって再帰関数にしたけれどわかりにくい。あとコレクションのコピーが重い。
~~そもそも早さを求める人はC#は使わないだろうが~~

まぁ愚直に作るとN次の繰り返しになるので仕方ないね。次元を減らさない限り。
なにはともあれ、100点をいただくことができました。やったぜ。

おわりに

ちょっと時間がかかってしまいましたが、解くことができました。
頭のトレーニングにはちょうどいいですね。

次はオブジェクト指向的にモデリングしてみても面白いかも。。なんて。
以上です。

※初投稿のため、気になった点・マサカリがあれば教えていただけると幸いです。