seki&竹間智能

原題によると、N個の商品、M種のコースがあります.
標準解法:
1、必要なデータ構造:

  private static Set items;
  private static ArrayList> groups;
  private static HashMap,ArrayList> status;

2、データ構造説明:

  items：        id，     
  groups：    ，           
  status：                ，   key      ，   value           （          ）

3、問題を解く核心的な考え:

               setA={a,b,c,d}  ，      setB={e,f}，  ：

        setX = setA+setB = {a,b,c,d,e,f}

       （                   "  "  ）。

4、解題のステップ:

  1.        set={},   status ；
  2.        group_i:
  3.             status_i:
  4.          group_i status_i     ，        ，   status ；
             //        status_i        +group_i     
  5.   status       ，  size()     ，     ；

5、いくつかの簡単で効果的な最適化:

  1.               ，    
  2.              ，    
  3.                  ，    
  4.        ，              ，            
  5.        4              ，      5        
  6.     （         <=32 ）：
                     (2^n)，             （          ， 0 1），       2        。
          ，    X    A4,A3,A1，     1101（   ），    Y    A6,A2，     100010（   ）。                   101111（   ）。
          ，              Set     Integer， ：
        private static ArrayList groups;
        private static HashMap> status;
              ，       （  、  、   ）              ，      O(n)   O(1)。

6、時間の複雑さの証明:

  1.                ，  status         2^n；
  2.         ，status size()      ，  status         2^m；
  3.          O(2^min(n,m))

この問題のいくつかの拡張思考について:元の問題は、コースを満たすための物品セットの10%割引、つまり商品ごとの重量が等しいです.セットごとに総価格を出すなら、一番安いセットの組み合わせを求めますか?つまり、各コースの「key」は依然として商品群です.「value」は商品の数ではなく、具体的な値です.つまり、各コースは次のように表しています.
コースID
商品IDグループ
トータル$
G 1
A 1,A 2,A 3,A 4,A 5,A 6
1600
G 2
A 1,A 2,A 50
1200
このように、元々の核心解題の考え方を少し修正すればいいです.
元:

               setA={a,b,c,d}  ，      setB={e,f}，  ：

        setX = setA+setB = {a,b,c,d,e,f}

       。

変更:

               setA={a,b,c,d}       valueA，    setB={e,f}     valueB， setX={a,b,c,d,e,f}       valueX（       ），  ：

        setX = min{ valueA+valueB , valueX }

                    （     ）。

必要なデータ構造は以下の通りです.

  //      id，Double         
  private static ArrayList items;

  //   Entry      ，Entry  key(Integer)         (             ),value(Double)        
  private static ArrayList> groups;

  //HashMap             。        key(HashMap)             (         )     ，value(ArrayList)        。
  private static HashMap,ArrayList> status;

このように処理した後に、すべての可能な状態を計算し終わった後に、すべての状態を遍歴してそしてそれとセットの中で商品の原価の総計を求めて、最低の総価は最も良い解です.