3

状況は、部屋をx人の人数で埋めなければならないということです。この例では、次を使用できます。

$persons = 7;

そして、次の配列を取得しました：

$differentRoom = array(
    'Room 1' => 1, //This room fits 1 person
    'Room 2' => 2, //This room fits 2 persons
    'Room 3' => 3, //This room fits 3 persons
);

今私はPHPが最短の方法で正確に7の組み合わせを作ることを望んでいます. 結果は次のようになります: 'Room3' 'Room 3' 'Room 1'

私が持っている別の例では

$persons = 15;

そして、配列

$differentRooms = array(
    'Room 1' => 4, // This room fits x persons
    'Room 2' => 7,
);

今回は組み合わせが正確に 15 になることはありません。この状況では、結果は 15 を超える組み合わせでなければなりません。この場合は 16 になります。16 は 10 に最も近く、結果はそうでなければなりません。必要なもの: 'Room 2''Room 2' 'Room 1'

これどうやってするの？

4

2 に答える 2

2

この問題は NP 困難であり、反復を伴うナップザック問題の変形です (この件に関する詳細についてはhttp://en.wikipedia.org/wiki/Knapsack_problemを参照してください)。

注目すべき変更点は、可能な限り最大の重みを取得しようとする代わりに、特定の値にできるだけ近い重みを取得しようとしていることです。これは、重み関数を変更することで実行できます。

そのための最良の解決策は動的プログラミングです。これについて調べてみてください。ただし、これはアルゴリズム/CSci に関する質問なので、数学/プログラミングのスタックエクスチェンジの質問掲示板に投稿することをお勧めします。

于 2013-05-16T13:39:40.723 に答える