部分和問題、アルゴリズムについての質問

Question

質問内容

以下の問題についてどういった方針で解くのが最適なのか教えていただきたいです。

問

ある製作物に必要な材料が記載されたレシピがあります。

例
椅子：　　木
家：　　　木、鉄、石
剣：　　　鉄
ノコギリ：　木、鉄

あなたに材料が与えられます。
例
木、石、鉄

与えられる材料は必ず１種類につき１つです。

レシピと与えられる材料を入力として
出来るだけ材料を使い切って得られる製作物を全通り出力について確認してください。
（残った材料で作ることのできるレシピがあれば作らなければならない）

出力例
ノコギリ
家
椅子、剣

制約

レシピ数　材料共に１０以下

私の考えた解き方

まず考えられるのはそれぞれのレシピで
作る作らないの２通りについて全通りみるというやり方です。

２^N（レシピ数）かかってしまうのでどうしても効率が悪いです。

部分和の問題に似ているので動的計画法を使えるのかなとも考えましたが実装の方針が立ちませんでした。

Comments

[BeatStar]

レシピ数(?) と、材料の数はどのぐらいでしょうか。
こういう競技プログラミング系や課題系って、大抵条件があるはずです。

N≦16 とかなのか、N≦100 とかなのかで使えるアルゴリズムが変わってくる気がします。

[NaokiNakamichi]

質問ありがとうございます。
追記いたしました。
材料とレシピ共に10以下です。

[swordone]

最初の例、剣とノコギリは同時に作れないのでは？

[NaokiNakamichi]

ありがとうございます。
出力を訂正しました。

[Zuishin]

高々 10 なら一番効率が悪い方法でもタイムアウトにならないでしょう。自分でやってみたコードを書いてみては？

Answer 1

木、石、鉄

これのグループ分け全パターンを調べるだけではないでしょうか．
（「木」とかだとタイピングが面倒なので，以下，ABCで書きますが）

• {A,B,C}
• {A,B}, {C}
• {A,C}, {B}
• {B,C}, {A}
• {A}, {B}, {C}

この中で，
全てのグループに見合うレシピがあるやつだけ
１つ以上のグループがレシピと合うやつだけ
を出力すればよい．

---

[追記]
実装してみたけど，「これはひどい」と言いたくなるコードになった…
（特に，材料のグループ分け全パターンを探すところがひどい有様）

//EnumGroupingPtn()が使う作業関数
void EnumPtnWork(
    const std::vector<unsigned int> &Mat,
    std::vector< std::vector<unsigned int> > &Result,
    int idx,
    const std::vector< unsigned int > &Curr
)
{
    if( idx == Mat.size() )
    {   Result.push_back( Curr );   return; }

    for( int i=0; i<Curr.size(); ++i )
    {
        std::vector<unsigned int> C = Curr;
        C[i] |= Mat[idx];
        EnumPtnWork( Mat, Result, idx+1, C );
    }

    std::vector<unsigned int> C = Curr;
    C.push_back( Mat[idx] );
    EnumPtnWork( Mat, Result, idx+1, C );
}

//材料のグループ分けパターンを全パターン列挙した結果を作る
std::vector< std::vector<unsigned int> > EnumGroupingPtn( const std::vector<unsigned int> &Materials )
{
    std::vector< std::vector<unsigned int> > Result;
    EnumPtnWork( Materials, Result, 0, std::vector<unsigned int>() );
    return Result;
}

//main
int main(void)
{
    //材料の種類要定数：bitパターンで表す
    const unsigned int Stone = 0x01;
    const unsigned int Wood = 0x01 << 1;
    const unsigned int Iron = 0x02 << 2;

    //レシピ
    //  key = 作るのに必要な材料の組み合わせ
    //  value = <成果物の種類を表す定数(bitパターン), 成果物名称>
    const std::map< unsigned int, std::pair<unsigned int, std::string> > Recipies
    {
        { Wood, { 0x1, "椅子" } },
        { Wood|Iron|Stone, { 0x1<<1, "家" } },
        { Iron, { 0x1<<2, "剣" } },
        { Wood|Iron, { 0x1<<3, "ノコギリ" } }
    };

    //与えられた材料
    const std::vector<unsigned int> Materials{ Stone, Wood, Iron };

    //結果用データ
    //  vector of < 成果物の組み合わせを示す値, 表示用文字列 >
    std::vector< std::pair<unsigned int,std::string> > Result;

    {//メインの処理：材料のグループ分け全パターンについて調査する
        for( const auto &MatGroups : EnumGroupingPtn( Materials ) )
        {
            //このグループ分けで作れる成果物群を調査
            std::string Str_for_Disp;   //※これは単なる結果表示用文字列
            unsigned int CraftPtn = 0;
            for( unsigned int MG : MatGroups )
            {
                auto iRecipie = Recipies.find( MG );
                if( iRecipie != Recipies.end() )
                {
                    if( CraftPtn>0 )Str_for_Disp += ", ";
                    Str_for_Disp += iRecipie->second.second;

                    CraftPtn |= iRecipie->second.first;
                }
            }
            if( CraftPtn==0 )continue;  //何も作れない場合

            //何か作れる場合
            bool Rejected = false;
            for( auto i=Result.begin(); i!=Result.end(); /*NOP*/ )
            {
                unsigned int And = ( i->first & CraftPtn );

                if( And == CraftPtn )   //既存よりも作れる物が少ない→このパターンを棄却
                {   Rejected=true;  break;  }
                else if( And == i->first )  //既存よりもたくさん作れる→既存を棄却
                {   i = Result.erase( i );  }
                else
                {   ++i;    }
            }

            if( !Rejected ) //棄却されなかったならResultに追加
            {   Result.emplace_back( CraftPtn, Str_for_Disp );  }
        }
    }

    //結果表示
    for( const auto &r : Result )
    {   std::cout << r.second << std::endl; }

    return 0;
}

Comments

[Zuishin]

よく読むと材料は余っても良いみたいですね。

[fana]

材料余りOKになるよう，修正しました．

Answer 2

（パズルゲームをプログラムに解かせるのが趣味でもあるので、こういうの好きです）

で、全レシピに対してつくる・つくらないの総あたりだと、
条件「残った材料で作ることのできるレシピがあれば作らなければならない」
を満たさないものを除くのが、またひと手間になるような。

さしあたり、高速探索の肝になるロジックとして、

●材料１点を1ビットに割り当て、レシピはビットパターンに。
●ビット演算 (手持ち材料 & レシピ材料) == レシピ.材料 なら造れる
●ビット演算 手持ち材料 &= ~レシピ.材料 で造ったあとの手持ち材料

のビット演算を使い再帰的にグリグリ回したいですね。

フローを書くとこんな感じでしょうか。

－－－

//sourceはc#風、ということで。(^^;

名前と材料(uint)をメンバ変数にもつ レシピclass

List<レシピ> レシピ帳;  //<------------------------材料点数の多いレシピほど後ろになるようにSort
List<string> 造れるレシピあれこれ;

再帰的に調べる関数(int 探索開始点, uint 手持ち材料, string 造れるレシピ)
{
    for (int i = 探索開始点; i < レシピ帳.Count; i++)
    {
        レシピ = レシピ帳[i];
        if ((手持ち材料 & レシピ.材料) == レシピ.材料)
        {
            // 作れる
            再帰的に調べる関数(i + 1, 手持ち材料, 造れるレシピ); 
            //（↑）それをあえて使わないパターンを再帰的に調べ上げる。
            
            造れるレシピ += レシピ.名前;
            手持ち材料 &= ~レシピ.材料;
            if (PopCount(手持ち材料) == 0)
            {
                造れるレシピあれこれ.Add(造れるレシピ);
                return;
            }
            if (PopCount(レシピ.材料) > PopCount(手持ち材料)) break;
        }
    }

    for (int i = 0; i < レシピ帳.Count; i++)
    {
        レシピ = レシピ帳[i];
        if ((手持ち材料 & レシピ.材料) == レシピ.材料)
        {
            return; //重複要素なので探索終了
        }
    }
    //余った材料で作れるレシピがないならそれも答えのひとつ
    造れるレシピあれこれ.Add(造れるレシピ);
}

基本は総当たり的になるのは必然ですが、
材料点数において、手持ち数以上を必要とするレシピは絶対造れない、とか、
高速化を図る余地はあるでしょう。
そのあたりは実際のレシピ数、材料数のボリュームに応じて改造すればよろしいかと。

それと、レシピclassの材料を、
必要bit数を満たす配列にして演算子をオーバーロードすれば、
材料点数64(ulong)超えても対応できるかと。

Answer 3

間違っている可能性もありますから、話半分で読んでください。
(私自身は数学苦手なため……)

私なら、bit全探索でやると思います。

DPでもいいですが、大掛かりすぎる気がします。
(bit全探索でもきついなら仕方ないですが)

bit全探索だと、どうしても 2^n かかりますが、n≦10 らしいので、1分間で処理できるものだと思います。

計算量オーダーの求め方を総整理！ 〜 どこから log が出て来るか 〜 によると、

11 秒間で処理できる for 文ループの回数は、108=100,000,000108=100,000,000 回程度

とあります。

それで、(以前ですが)計算してみると、処理部だけに注目してみると、n = 16 までは耐えられるようです。

処理部だけで、なので実際にはもっと少ないと思います。(入力部とかもあるし……)

でも今回の場合、n≦10 なので おそらく耐えられるはずです。2^n でも。

もしbit全探索でやるなら、

私ならまず レシピ系のやつをクラスオブジェクトなり構造体オブジェクトなりのものにしてまとめる。
そして、C言語なら関数を介して調べますが、C++とかJavaとかのようなOOP系言語ならメソッド(メンバ関数)を介して、

if( obj.isValid( ビットで取得したデータ列 ) )...

のようにしてレシピの材料品目(?)に一致するかどうかとかを調べます。

そして、一致するものを候補みたいに保持するか表示する。

二品目以上のやつは……どうでしょうねぇ……二品目だけなら、if文で『ビットが立っている』ときと『立っていない時』の分岐でやるっていうのはどうでしょうか。
三品目以上ある場合は……すみませんわかりません。

Comments

[NaokiNakamichi]

回答ありがとうございます！
やはりこの問題は２^Nで解くのがいいのでしょうか...
計算量の話など参考になる話をいただき大変ためになりました！

[BeatStar]

私は数学苦手なので確実な事は言えませんが、プログラミングには絶対的な正解はありません。

たまたまですが、 https://atcoder-tags.herokuapp.com/explain がありました。
このサイトでは「Stack」の分類にあるものが、C++でいう std::atackを使わずにやっている回答もあるようです。

つまり、仕様に沿っていて、制限時間以内に、かつ処理時間がリミットを超えないならそれでいいようです。

もしどうしてもbit全探索でも単純な全探索でも「タイムオーバー」系のエラーになったらDPとかみたいなものでもいいと思います。